2239 - pow2

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

Cerinţa

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

Iesire

Datele de intrare corespund restrictiilor impuse
4

Exemplul 2

Intrare

210000
16 17 20 24 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105

Iesire

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line> def is_power_of_two(num):

   return (num != 0) and (num & (num-1) == 0)

num_elements = int(input().strip()) if not (2 <= num_elements <= 100000):

   print("Datele de intrare nu corespund restrictiilor impuse")
   exit(1)

a = sorted(list(map(int, input().split()))) if any(ai < 1 or ai > 1000000000 for ai in a):

   print("Datele de intrare nu corespund restrictiilor impuse")
   exit(1)

print("Datele de intrare corespund restrictiilor impuse")

count = 0 for i in range(num_elements):

   for j in range(i+1, num_elements):
       if is_power_of_two(a[i] + a[j]):
           count += 1

print(count) </syntaxhighlight>

Explicație

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