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
Răspunsuri la întrebare
Răspuns de
0
#include <iostream>
using namespace std;
int cn, n, a[512], s[512];
bool este_putere_la_doi(int x)
{
return !(x & (x - 1));
}
void c_binara(int lhs, int rhs)
{
if (lhs < rhs)
{
if (rhs - lhs == 1)
{
if (este_putere_la_doi(s[lhs]))
++cn;
}
else
{
int jum = (lhs + rhs) / 2;
c_binara(lhs, jum);
c_binara(jum, rhs);
}
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 0; i < n - 1; ++i)
for (int j = i + 1; j < n; ++j)
s[cn++] = a[i] + a[j];
n = cn;
cn = 0;
c_binara(0, n);
std::cout << cn;
}
Alte întrebări interesante
Matematică,
8 ani în urmă
Limba română,
8 ani în urmă
Chimie,
8 ani în urmă
Limba română,
8 ani în urmă
Matematică,
9 ani în urmă
Limba română,
9 ani în urmă