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, …

Exemplul 1

Intrare

4

3 5 3 13

Ieșire

Datele de intrare corespund restrictiilor impuse.

4

Exemplul 2

Intrare

4

a

Ieșire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

def verificare_restrictii(nr_n, nr_a):    # functia de verificare a datelor de intrare
    if 2 <= nr_n <= 10**5 and all(1 <= a_i <= 10**9 for a_i in nr_a):
        return True
    else:
        return False


def numar_perechi(nr_n, nr_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
    nr_perechi = 0

    # Parcurgem fiecare element din lista a
    for i in range(nr_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 < nr_a[i]:
                continue

            # Calculăm numărul pe care îl căutăm în contor
            numar_cautat = putere - nr_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
                nr_perechi += contor[numar_cautat]

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

    return nr_perechi


if __name__ == '__main__':
    try:
        n = int(input("Introduceti numarul n: "))     # citirea numarului de linii si coloane
        a = list(map(int, input().split()))

        if verificare_restrictii(n, a):             # verificam datele de intrare
            print("Datele de intrare corespund restrictiilor impuse.")
            print(numar_perechi(n, a))                           # apelam functia de rezolvare
        else:
            print("Datele de intrare nu corespund restrictiilor impuse.")
    # ne asteptam la 2 tipuri de erori din cauza datelor de intrare, le tratam corespunzator
    except ValueError:
        print("Datele de intrare nu corespund restrictiilor impuse.")
    except IndexError:
        print("Datele de intrare nu corespund restrictiilor impuse.")

Explicatii

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