Editing 2239 - Pow2

Se consideră un șir '''a[1]''', '''a[2]''',…, '''a[n]''' de numere naturale nenule.

==Cerință==

Să se determine câte perechi de indici '''(i, j), 1 ≤ i < j ≤ n''', există cu proprietatea că suma '''a[i] + a[j]''' este egală cu o putere a lui 2.

==Date de intrare==

Programul citește de la tastatură numărul '''n''', iar apoi cele '''n''' numere naturale nenule, separate prin spații.

==Date de ieșire==

Programul va afișa pe ecran un singur număr natural reprezentând numărul de perechi de indici distincți '''(i, j)''' cu proprietatea că suma '''a[i] + a[j]''' este egală cu o putere a lui 2.

==Restricții și precizări==

*'''2 ≤ n ≤ 100.000'''
*'''1 ≤ a[i] ≤ 1.000.000.000''', pentru orice '''i = 1..n'''
*Numerele care sunt puteri ale lui 2 sunt 1, 2, 4, 8, 16, 32, …

==Exemplu==

;Intrare
:4
:3 5 3 13

;Ieșire
:4

==Rezolvare==
<syntaxhighlight lang="python" line="1" start="1">

def numar_perechi(n, a):
    # Generăm toate puterile lui 2 până la 2^30
    puteri_de_doi = [2**i for i in range(31)]

    # Inițializăm un contor pentru fiecare număr posibil din șir
    contor = [0]*2000001

    # Inițializăm numărul de perechi cu 0
    numar_perechi = 0

    # Parcurgem fiecare element din lista a
    for i in range(n):
        # Pentru fiecare element, parcurgem lista de puteri ale lui 2
        for putere in puteri_de_doi:
            # Dacă puterea lui 2 este mai mică decât numărul curent, trecem la următoarea putere
            if putere < a[i]:
                continue

            # Calculăm numărul pe care îl căutăm în contor
            numar_cautat = putere - a[i]

            # Dacă numărul căutat este în intervalul contorului
            if numar_cautat <= 2000000:
                # Adăugăm la numărul de perechi numărul de apariții al numărului căutat
                numar_perechi += contor[numar_cautat]

        # Dacă numărul curent este în intervalul contorului
        if a[i] <= 2000000:
            # Incrementăm contorul pentru numărul curent
            contor[a[i]] += 1

    return numar_perechi

# Citim datele de intrare
n = int(input())
a = list(map(int, input().split()))

# Apelăm funcția și afișăm rezultatul
print(numar_perechi(n, a))

</syntaxhighlight>

==Explicatii==

Cele patru perechi de indici sunt: (1,2), (1,4), (2,3), (3,4).