Question

Buna!
Ma puteti ajuta la problema aceasta??

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

Exemplu
Intrare

4
3 5 3 13
Ieșire

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

Answer 1

Răspuns:

Momentan o sa iti zic ideea din spatele problemei, iar daca nu te descurci ma intrebi. O abordare eficienta a acestei probleme este urmatorea:

- iti precalculezi puterile lui 2 pana in 2 ^ 30 cred , in care pe indicele i  ai puterea lui 2 cu exponentul i.

- sortezi vectorul

- te plimbi prin numerele din vector si prin puteri (for in for) si cauti binar p[j] - a[i] (p - vectorul cu puteri , a - vectorul cu numere)

- am uitat sa mentionez faptul ca trebuie sa ai grija la implementare cu mici optimizari: ai nevoie de un vector de frecventa si trebuie sa ai grija la lucrurile de genul  2 2 2 2, te las pe tine sa descoperi regula :)

Succes