Codeforces Solution-C. Summarize to the Power of Two-Solution in C, C++, Java, Python

Algorithm

A sequence $a_{1}, a_{2}, \dots, a_{n}$ is called good if, for each element $a_{i}$ , there exists an element $a_{j}$ ( $i \neq j$ ) such that $a_{i} + a_{j}$ is a power of two (that is, $2^{d}$ for some non-negative integer $d$ ).

For example, the following sequences are good:

$[5, 3, 11]$ (for example, for $a_{1} = 5$ we can choose $a_{2} = 3$ . Note that their sum is a power of two. Similarly, such an element can be found for $a_{2}$ and $a_{3}$ ),
$[1, 1, 1, 1023]$ ,
$[7, 39, 89, 25, 89]$ ,
$[]$ .

Note that, by definition, an empty sequence (with a length of $0$ ) is good.

For example, the following sequences are not good:

$[16]$ (for $a_{1} = 16$ , it is impossible to find another element $a_{j}$ such that their sum is a power of two),
$[4, 16]$ (for $a_{1} = 4$ , it is impossible to find another element $a_{j}$ such that their sum is a power of two),
$[1, 3, 2, 8, 8, 8]$ (for $a_{3} = 2$ , it is impossible to find another element $a_{j}$ such that their sum is a power of two).

You are given a sequence $a_{1}, a_{2}, \dots, a_{n}$ . What is the minimum number of elements you need to remove to make it good? You can delete an arbitrary set of elements.

Input

The first line contains the integer $n$ ( $1 \leq n \leq 120000$ ) — the length of the given sequence.

The second line contains the sequence of integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{9}$ ).

Output

Print the minimum number of elements needed to be removed from the given sequence in order to make it good. It is possible that you need to delete all $n$ elements, make it empty, and thus get a good sequence.

Examples
input
Copy
6
4 7 1 5 4 9
output
Copy
1
input
Copy
5
1 2 3 4 5
output
Copy
2
input
Copy
1
16
output
Copy
1
input
Copy
4
1 1 1 1023
output
Copy
0

Note

In the first example, it is enough to delete one element $a_{4} = 5$ . The remaining elements form the sequence $[4, 7, 1, 4, 9]$ , which is good.

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 1;
int n, a[N], powers[32];

int main() {
  for(int i = 0; i < 32; ++i)
    powers[i] = 1 << i;

  scanf("%d", &n);
  for(int i = 0; i < n; ++i)
    scanf("%d", a + i);
  sort(a, a + n);

  int res = 0;
  for(int i = 0; i < n; ++i) {
    bool ok = false;
    for(int j = 0; j < 32; ++j)
      if(powers[j] > a[i]) {
        int idx = lower_bound(a, a + n, powers[j] - a[i]) - a;
        if(a[idx] + a[i] == powers[j])
          if(idx != i || (idx + 1 < n && a[idx + 1] == a[idx])) {
            ok = true;
            break;
          }
      }
    res += !ok;
  }

  printf("%d\n", res);

  return 0;
}

Copy The Code & Try With Live Editor

Input

–

cmd

6
4 7 1 5 4 9

Output

–

cmd

Demonstration

Codeforces Solution-C. Summarize to the Power of Two-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution

Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+

Try With Live Editor

Category - Codeforces Online Judge Maniruzzaman Akash 1 year ago 279 0