codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

702B.md (1073B)


      1 Source: https://codeforces.com/problemset/problem/702/B
      2 
      3 B. Powers of Two
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given *n* integers *a*1, *a*2, ..., *a**n*. Find the number of pairs of indexes *i*, *j* (*i* < *j*) that *a**i* + *a**j* is a power of 2 (i. e. some integer *x* exists so that *a**i* + *a**j* = 2*x*).
     22 
     23 Input
     24 
     25 The first line contains the single positive integer *n* (1 ≤ *n* ≤ 105) — the number of integers.
     26 
     27 The second line contains *n* positive integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 109).
     28 
     29 Output
     30 
     31 Print the number of pairs of indexes *i*, *j* (*i* < *j*) that *a**i* + *a**j* is a power of 2.
     32 
     33 Examples
     34 
     35 Input
     36 
     37 ```
     38 4  
     39 7 3 2 1
     40 ```
     41 
     42 Output
     43 
     44 ```
     45 2
     46 ```
     47 
     48 Input
     49 
     50 ```
     51 3  
     52 1 1 1
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 3
     59 ```
     60 
     61 Note
     62 
     63 In the first example the following pairs of indexes include in answer: (1, 4) and (2, 4).
     64 
     65 In the second example all pairs of indexes (*i*, *j*) (where *i* < *j*) include in answer.