Problem:
 Score : 600 points    Problem Statement Takahashi has N balls with positive integers written on them. The integer written on the i -th ball is A_i .
He would like to form some number of pairs such that the sum of the integers written on each pair of balls is a power of 2 .
Note that a ball cannot belong to multiple pairs.
Find the maximum possible number of pairs that can be formed.  Here, a positive integer is said to be a power of 2 when it can be written as 2^t using some non-negative integer t .      Constraints  1 \leq N \leq 2\times 10^5  1 \leq A_i \leq 10^9  A_i is an integer.         Input Input is given from Standard Input in the following format:  N  A_1  A_2  ...  A_N       Output Print the maximum possible number of pairs such that the sum of the integers written on each pair of balls is a power of 2 .        Sample Input 1 3
1 2 3      Sample Output 1 1  We can form one pair whose sum of the written numbers is 4 by pairing the first and third balls.
Note that we cannot pair the second ball with itself.       Sample Input 2 5
3 11 14 5 13      Sample Output 2 2

Solution (Python):
N = int(input())
A_list = list(map(int, input().split()))
two_list = [2 ** i for i in range(32)]

count = 0
items = {}
for a in A_list:
    if a in items.keys():
        items[a] += 1
    else:
        items[a] = 1
A_list.sort(reverse=True)
import bisect

for a in A_list:
    if items[a] >= 1:
        index = bisect.bisect_left(two_list, a)
        for t in two_list[index:]:
            m = t - a
            if m in items.keys():
                if m == a and items[a] >= 2:
                    count += 1
                    items[a] -= 2
                    break

                elif m != a and items[m] >= 1 and items[a] >= 1:
                    count += 1
                    items[a] -= 1
                    items[m] -= 1
                    break
print(count)

Solution (Python):
from collections import Counter

N = int(input())
As = list(map(int, input().split()))

cnt = Counter(As)
As.sort(reverse=True)

Ps = [2]
for i in range(29):
    Ps.append(Ps[-1] * 2)

ans = 0
for A in As:
    if cnt[A] <= 0: continue
    cnt[A] -= 1

    while Ps[-1] > 2 * A:
        Ps.pop()

    if cnt[Ps[-1] - A] > 0:
        ans += 1
        cnt[Ps[-1] - A] -= 1

print(ans)

Solution (Python):
import collections
N=int(input())
x=list(map(int,input().split()))
c=collections.Counter(x)
t=[2**i for i in range(len(str(bin(max(x)*2))[2:])+1)[::-1]]
count=0
start=0
x.sort()
for i in range(len(x))[::-1]:
    for j in range(start,len(t)):
        if t[j] > 2*x[i]:
            start = j
        if t[j] < x[i]:
            break
        if t[j]-x[i] in c.keys():
            if t[j]-x[i] == x[i]:
                if c[x[i]] >= 2:
                    c[x[i]] -= 2
                    count +=1
            else:
                if c[t[j]-x[i]]>0 and c[x[i]]>0:
                    c[t[j]-x[i]] -= 1
                    c[x[i]] -= 1
                    count+=1
print(count)

Solution (Python):
from collections import Counter
n = int(input())
A = sorted(list(map(int, input().split())))[-1::-1]
c = Counter(A)
ans = 0
for a in A:
    b = (1<<a.bit_length()) - a
    if a == b and c[a] > 1:
        c[a] -= 2
        ans += 1
    elif a != b and c[a] > 0 and c[b] > 0:
        c[a] -= 1
        c[b] -= 1
        ans += 1
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split(" ")))
A.sort()
used = [0] * N
pow2_set = reversed([ 1<<i for i in range(36)])
ans = 0
for pow2 in pow2_set:
    l,r = 0,N-1
    while l < r:
        if A[l] + A[r] < pow2:
            l += 1
        elif A[l] + A[r] == pow2:
            if used[l] == 0 and used[r] == 0:
                ans += 1
                used[l],used[r] = 1,1
            else:
                if used[l] == 1:
                    l += 1
                if used[r] == 1:
                    r -= 1
        else:
            r -= 1

print(ans)

Solution (Python):
from collections import defaultdict
def twopower(n):
    for i in range(32):
        if n < 2**i:
            return 2**i
N = int( input())
A = list( map( int, input().split()))
d = defaultdict( int)
e = defaultdict( int)
for i in range(N):
    d[A[i]] += 1
A.sort(reverse=True)
i = 0
ans = 0
while i < N:
    if e[A[i]] >= d[A[i]]:
        i += 1
        continue
    e[A[i]] += 1
    L = twopower(A[i]) - A[i]
    if e[L] < d[L]:
        ans += 1
        e[L] += 1
    i += 1
print(ans)

Solution (Python):
import bisect
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
H = defaultdict(lambda: [])
Ad = defaultdict(lambda: 0)
N = int(input())
A = inpl()
for i in A:
    Ad[i] += 1
A = list(set(A))
A.sort()
ans = 0
for j in range(30,0,-1):
    k = 2**j
    H = defaultdict(lambda: [])
    ml = bisect.bisect_left(A, k) 
    for i in A[:ml]:
        if 2*i == k:
            ans += Ad[i]//2
            del Ad[i]
            continue
        if H[k-i]:
            m = min(Ad[k-i], Ad[i])
            Ad[k-i] -= m
            del Ad[i]
            ans += m
        else:
            H[i] = j
print(ans)

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]

n=i1()
a=i2()
from collections import defaultdict
d = defaultdict(int)
for i in a:
 d[i]+=1
a.sort()
import math
f=0
for i in range(n)[::-1]:
 if d[a[i]]>0:
  x=2**(int(math.log2(a[i]))+1)-a[i]
  d[a[i]]-=1
  if d[x]>0:
    d[x]-=1
    f+=1
  else:
    d[a[i]]+=1
print(f)

Solution (Python):
import collections
n = int(input())
a = list(map(int, input().split()))

memo = collections.defaultdict(lambda : 0)

for i in a:
    memo[i] = memo[i] + 1

b = sorted(memo.keys(), reverse=True)

ret = 0
pot = [1] * 35
for i in range(len(pot)-1):
    pot[i+1] = pot[i] * 2

for i in b:
    for j in range(34, -1, -1):
        if pot[j] - i <= 0:
            t = pot[j+1] - i
            break

    if i == t:
        ret += memo[i] // 2
    else:
        c = min([memo[i], memo[t]])
        memo[t] -= c
        ret += c

print(ret)

Solution (Python):

import collections

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
c=collections.Counter(A)

pairCounter=0

beki=29
nibeki=2**beki

for i in range(N):
  target = A[i]
  if c[target] < 1:
    continue
  c[target]-= 1

  while (nibeki > target):
    beki-=1
    nibeki=2**beki

  pair = nibeki * 2 - target
  if pair in c.keys() and c[pair] > 0:
    c[pair]-= 1
    pairCounter+=1

print(pairCounter)

Solution (Python):
import collections
import math
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
c=collections.Counter(a)
ans=0
for i in a:
  j=int(math.log2(i))+1
  k=2**j-i
  if k in c.keys():
    if i==k and c[i]>1:
      c[i]-=2
      ans+=1
    elif i!=k and c[i]>0 and c[k]>0:
      c[i]-=1
      c[k]-=1
      ans+=1
print(ans)

Solution (Python):
from math import log,floor
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

A.sort(reverse=True)
C = Counter(A)

cnt = 0
last_a = -1
for i in range(N):
  a = A[i]
  if last_a == a:
    continue
  last_a = a
  count_a = C[a]
  if count_a <= 0:
    continue
  b = pow(2,floor(log(a)/log(2))+1) - a
  count_b = C[b]
  if count_b <= 0:
    continue
  i += count_a - 1
  x = min(count_a, count_b) if a != b else count_a // 2
  cnt += x
  C[a] -= x
  C[b] -= x
  
print(cnt)

Solution (Python):
import bisect
 
n = int(input())
a = list(map(int, input().split()))
a.sort()
 
res = 0
for i in range(n - 1 , -1, -1):
    if a[i] == int(a[i]):
        b = 1
        while b <= a[i]:
            b =b*2
 
        j = bisect.bisect_left(a, b - a[i])
        if i > j:
            if b - a[i] == a[j]:
                res += 1
                a[j] = a[j] - 0.5
                a[i] = a[i] + 0.5
print(res)

Solution (Python):

from collections import Counter
 
n = int(input())
a = list(map(int, input().split()))
a.sort()
a = a[::-1]
c = Counter(a)

res = 0
for x in a:
    b = 1
    while b <= x:
        b = b*2
    p = b-x
    if p in c.keys():
        if p == x and c[x] >= 2:
            c[x] = c[x] - 2
            res += 1
        elif p != x and c[x] > 0 and c[p] > 0:
            c[x] -= 1
            c[p] -= 1
            res += 1
    
print(res)

Solution (Python):
from collections import Counter

N = int(input())
A = list(map(int, input().split()))

A.sort(reverse=True)
c = Counter(A)
res = 0
for a in A:
    n = 2 ** a.bit_length() - a
    if n in c.keys():
        if a == n and c[a] > 1:
            c[a] -= 2
            res += 1
        elif a != n and c[a] > 0 and c[n] > 0:
            c[a] -= 1
            c[n] -= 1
            res += 1
    
print(res)

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
A.sort()
A.reverse()
c = Counter(A)
ans = 0





for e in A:

    if c[e] == 0:
        continue
    c[e] -= 1
    pair = pow(2,e.bit_length()) - e
    if c[pair] >= 1:
        ans += 1
        c[pair] -= 1
print(ans)

Solution (Python):
import math
N = int(input())
A = sorted([int(_) for _ in input().split()], reverse=True)
dp = {}
for a in A:
    dp[a] = dp.get(a, 0) + 1
ans = 0
for a in A:
    if dp[a]:
        dp[a] -= 1
        if dp.get(2**int(math.log2(a) + 1) - a, 0) > 0:
            dp[2**int(math.log2(a) + 1) - a] -= 1
            ans += 1
print(ans)

Solution (Python):
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
c = Counter(A)

ans = 0
for a in A:
    b = (1 << a.bit_length()) - a
    if b in c.keys():
        if a == b and c[a] > 1:
            c[a] -= 2
            ans += 1
        elif a != b and c[a] > 0 and c[b] > 0:
            c[a] -= 1
            c[b] -= 1
            ans += 1

print(ans)

Solution (Python):
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
c = Counter(A)

ans = 0
for a in A:
    b = (1 << a.bit_length()) - a
    if a == b and c[a] > 1:
        c[a] -= 2
        ans += 1
    elif a != b and c[a] > 0 and c[b] > 0:
        c[a] -= 1
        c[b] -= 1
        ans += 1

print(ans)

Solution (Python):
from bisect  import bisect_left

n = int(input())
a = list(map(int,input().split()))
a.sort()


sum = 0
for i in range (len(a)-1,-1,-1):

    b = 1
    while b <= a[i]:
        b = b<<1
    t = b - a[i]
    

    k = bisect_left(a,t)
    if a[k] == t and k < i:
        sum += 1
        a[k] -= 0.1
        a[i] += 0.1
print(sum)

Solution (Python):
import collections

N = input()
A = map(int, raw_input().split())
C = collections.Counter(A)
K = C.keys()
K.sort(reverse=1)
res = 0
for i in K:
    for j in xrange(60):
        p = 2 ** j
        if i <= p:
            break
    if i == p:
      res += C[i] // 2
      C[i] = C[i] // 2 * 2
    else:
      num = min(C[i], C[p - i])
      res += num
      C[i] -= num
      C[p - i] -= num
print res

Solution (Python):
from collections import Counter

n = int(input())
nums = sorted(list(map(int, input().split())), reverse=True)

num_map = Counter(nums)

answer = 0
for num in nums:
    pair = (1 << (num.bit_length())) - num

    if num_map[num] > 0 and num_map[pair]:
        if num == pair and num_map[num] > 1:
            answer += 1
            num_map[num] -= 2
        if not num == pair:
            answer += 1
            num_map[num] -= 1
            num_map[pair] -= 1

print(answer)

Solution (Python):
from collections import Counter

n = int(input())
nums = sorted(list(map(int, input().split())), reverse=True)

num_map = Counter(nums)

answer = 0
for num in nums:
    pair = (1 << (num.bit_length())) - num

    if num_map[num] > 0 and num_map[pair]:
        if num == pair and num_map[num] > 1:
            answer += 1
            num_map[num] -= 2
        if num > pair:
            answer += 1
            num_map[num] -= 1
            num_map[pair] -= 1

print(answer)

Solution (Python):



def 解():
    N = int(input())
    dA ={}
    def lenbin(a):
        return len(bin(a)) - 2
    def addData(oDict,a):
        if a in oDict:
            oDict[a]+=1
        else:
            oDict[a]=1
    for a in map(int,input().split()):
        addData(dA,a)
    def searchPair(oD):
        iC = 0
        for a in sorted(oD.keys(),reverse=True):
            if oD[a]:
                t = ( 1 << lenbin(a)) - a
                if t == a:
                    iAT = oD[a] // 2
                    iC += iAT
                    oD[a] -= iAT *2
                elif t in oD:
                    iAT = min(oD[a],oD[t])
                    iC += iAT
                    oD[a] -= iAT
                    oD[t] -= iAT
        return iC
    print(searchPair(dA))
解()

Solution (Python):
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))

a.sort()
memo = defaultdict(int)
for i in range(n):
    memo[a[i]] += 1

count = 0
for i in reversed(range(n)):
    if memo[a[i]] == 0:
        continue
    if (memo[(1 << (len(bin(a[i])) - 2)) - a[i]] > 0 and (1 << (len(bin(a[i])) - 2)) - a[i] != a[i]) or memo[(1 << (len(bin(a[i])) - 2)) - a[i]] > 1:
        memo[a[i]] -= 1
        memo[(1 << (len(bin(a[i])) - 2)) - a[i]] -= 1
        count += 1

print(count)

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
T=[2**i for i in range(1,35)]
table=[True]*N
A.sort()
ans=0
for t in T[::-1]:
  l,r=0,N-1
  while l<r:
    if A[l]+A[r]>t:
      r-=1
    elif A[l]+A[r]==t:
      if table[l] and table[r]:
        ans+=1
        table[l],table[r]=False,False
      if not table[l]:
        l+=1
      if not table[r]:
        r-=1
    elif A[l]+A[r]<t:
      l+=1
print(ans)

Solution (Python):
N = int(input())
dA1 ={}
dA0 ={}
def lenbin(a):
    return len(bin(a)) - 2
def addData(oDict,a):
    if a in oDict:
        oDict[a]+=1
    else:
        oDict[a]=1
for a in input().split():
    a = int(a)
    if a % 2 :
        addData(dA1,a)
    else:
        addData(dA0,a)
def searchPair(oD):
    iC = 0
    for a in sorted(oD.keys(),reverse=True):
        t = ( 1 << lenbin(a)) - a
        if t == a:
            iAT = oD[a] // 2
            iC += iAT
            oD[a] -= iAT *2
        elif t in oD:
            iAT = min(oD[a],oD[t])
            iC += iAT
            oD[a] -= iAT
            oD[t] -= iAT
    return iC



print(searchPair(dA1)+searchPair(dA0))

Solution (Python):
from collections import Counter

n = int(input())
A = list(map(int, input().split()))

A.sort(reverse=True)
c = Counter(A)

ans = 0
flag = False
for i in range(n):
    if c[A[i]] == 0:
        continue

    pow_2 = 2 ** len(format(A[i], "b"))
    if c[pow_2 - A[i]] > 0 and pow_2 - A[i] != A[i]:
        c[pow_2 - A[i]] -= 1
        c[A[i]] -= 1
        ans += 1
    elif c[pow_2 - A[i]] > 1 and pow_2 - A[i] == A[i]:
        if flag is True:
            c[A[i]] -= 2
            ans += 1
            flag = False
        else:
            flag = True

print(ans)

Solution (Python):
import math

N = int(input())
A = list(map(int,input().split()))

D = {}
for i in A :
    if i not in D : D[i] = 1
    else: D[i] += 1

A = sorted(A,reverse=True)
ans = 0
for i in range(N) :
    r = 2**(math.ceil(math.log2(A[i])))
    if A[i] == r :
        ans += (D[A[i]] // 2)
        D[A[i]] = 0
    else :
        b = r - A[i]
        if (D[A[i]] > 0) and (D.get(b,0) > 0) :
            ans += 1
            D[A[i]] -= 1
            D[b] -= 1
print(ans)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = list(li())

from collections import Counter

acnt = Counter(a)

ans = 0
temp = 0
for ai in sorted(a,reverse=True):
    pair = (1<<(ai.bit_length())) - ai
    
    if acnt[ai] > 0 and acnt[pair] > 0:
        if ai == pair:
            temp = (acnt[ai] // 2)
            ans += temp
            acnt[ai] -= (2*temp)
            
        elif ai > pair:
            temp = min(acnt[ai], acnt[pair])
            ans += temp
            acnt[ai] -= temp
            acnt[pair] -= temp
            
print(ans)

Solution (Python):
N=int(input())
A=list(map(int, input().split()))

A.sort(reverse=True)
dic={}
for a in A:
    dic[a]=dic.get(a,0)+1

ans=0

for a in A:
    small=(1<<(len(format(a,"b")))) -a
    if small==a:
        if dic[a]>=2:
            dic[a]-=2
            ans+=1
        continue
    if dic.get(a,0)>0 and dic.get(small,0)>0:
        dic[a]-=1
        dic[small]-=1
        ans+=1
print(ans)

Solution (Python):

N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)

b = {}
for c in a:
    try:
        b[c] += 1
    except:
        b[c] = 1


pow2 = 1
while pow2 <= a[0]:
    pow2 *= 2

cnt = 0
for aa in a:
    while  aa < (pow2//2):
        pow2 //= 2
    
    v = aa
    rem = pow2 - aa
    
    if (not v in b) or (not rem in b):
        continue

    if rem != v and (b[v] > 0 and b[rem] > 0):
        hit = min(b[v], b[rem])
        cnt += hit
        b[v] -= hit
        b[rem] -= hit
    elif rem == v and b[v] > 1:
        cnt += b[v]//2
        b[v] = b[v]%2

print(cnt)

Solution (Python):
import math
from collections import defaultdict

def main():
    n = int(input())
    nums = list(map(int, input().split()))
    nums.sort()

    nums_cnt = defaultdict(int)
    for num in nums:
        nums_cnt[num] += 1

    cnt = 0
    for num in reversed(nums):
        if nums_cnt[num] <= 0:
            continue

        power_of_2 = 1 << math.ceil(math.log2(num))
        pair = power_of_2 - num

        if pair != 0 and nums_cnt[pair] > 0:
            nums_cnt[pair] -= 1
            nums_cnt[num] -= 1
            cnt += 1
        elif pair == 0 and nums_cnt[num] >= 2:
            nums_cnt[num] -= 2
            cnt += 1

    print(cnt)
    return

main()

Solution (Python):
import math
from collections import defaultdict

def main():
    _ = int(input())
    nums = list(map(int, input().split()))
    n = len(nums)
    nums.sort()

    nums_cnt = defaultdict(int)
    for num in nums:
        nums_cnt[num] += 1

    cnt = 0
    

    for cur in reversed(range(n)):
        num = nums[cur]
        if nums_cnt[num] <= 0:
            continue

        power_of_2 = 1 << math.ceil(math.log2(num))

        pair = power_of_2 - num


        if pair != 0 and nums_cnt[pair] > 0:
            nums_cnt[pair] -= 1
            nums_cnt[num] -= 1
            cnt += 1
        elif pair == 0 and nums_cnt[num] >= 2:
            nums_cnt[num] -= 2
            cnt += 1


        '''
        idx = bisect.bisect_left(nums, pair)
        if idx >= cur or nums[idx] != pair:
            
            continue

        while used[idx]:
            idx += 1

        if nums[idx] == pair:
            used[idx] = True
            cnt += 1

        
        
        '''

        

    print(cnt)

    return

main()

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
dic = {}
for a in A:
    dic[a] = dic.get(a,0)+1
ans = 0

for a in A:
    small = (1<<(len(format(a,"b")))) - a
    if small == a:
        if dic[a] >= 2:
            dic[a] -= 2
            ans += 1
        continue
    if dic.get(a,0)>0 and dic.get(small,0)>0:
        dic[a] -= 1
        dic[small] -= 1
        ans += 1
print(ans)

Solution (Python):
from math import *
 
n=int(raw_input())
arr=list(map(int,raw_input().split()))
dict1={}
for i in range(n):
    val=arr[i]
    try:
        dict1[val]+=1
    except:
        KeyError
        dict1[val]=1

ans=0
arr.sort(reverse=True)
for i in range(n):
    if(dict1[arr[i]]>0):
        xd=2**(len(bin(arr[i]))-2)
        if(xd-arr[i]!=arr[i]):
            try:
                if(dict1[xd-arr[i]]>0):
                    ans+=1
                    dict1[xd-arr[i]]-=1
                    dict1[arr[i]]-=1
            except:
                KeyError
        else:
            if(dict1[arr[i]]>1):
                ans+=1
                dict1[arr[i]]-=2
print(ans)

Solution (Python):
def b_powers_of_two(N, A):
    
    from bisect import bisect_left
    a = sorted(A)
    ans = 0
    for j in range(N - 1, -1, -1):
        
        b = 1
        while b <= a[j]:
            b <<= 1

        k = bisect_left(a, b - a[j])
        if k < j and (b - a[j] == a[k]):
            
            
            
            ans += 1
            
            
            
            
            a[j] += 0.1
            a[k] -= 0.1

    return ans

N = int(input())
A = [int(i) for i in input().split()]
print(b_powers_of_two(N, A))

Solution (Python):
from collections import Counter

def larger_nibeki(i):
	return 2 ** len(format(i, "b"))

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = 0
c = Counter(a)

for i in range(n):
	if c[a[i]] == 0:
		continue
	else:
		c[a[i]] -= 1
		if c[larger_nibeki(a[i]) - a[i]] > 0:
			ans += 1
			c[larger_nibeki(a[i]) - a[i]] -= 1

print(ans)

Solution (Python):
import math

N = int(input())
a = sorted(list(map(int,input().split())))

count = 0

b = {}
for i in range(len(a)):
    if a[i] in b:
        b[a[i]] += 1
    else:
        b[a[i]] = 1

for i in range(len(a) - 1, -1, -1):
    if  b[a[i]] == 0:
        continue
    temp = a[i]
    b[a[i]] -= 1
    s=2**math.floor(math.log2(temp))
    st = 2*s - temp 
    if a ==[]:
        break
    if st in b and b[st] > 0:
        b[2*s-temp] -= 1
        count += 1
    
print(count)

Solution (Python):
def solve(C):
    ans = 0
    for a in sorted(C, reverse=True):
        if C[a] <= 0:
            continue
        ma = 1 << a.bit_length()
        b = ma - a
        if b in C and C[b] > 0:
            if a == b:
                pair = C[a] // 2
            else:
                pair = min(C[a], C[b])
                C[b] -= pair
            ans += pair
    return ans

from collections import defaultdict
N, *A = map(int, open(0).read().split())
C_e = defaultdict(int)
C_o = defaultdict(int)
for a in A:
    if a % 2 == 0:
        C_e[a] += 1
    else:
        C_o[a] += 1
print(solve(C_e) + solve(C_o))

Solution (Python):
from collections import Counter

n= int(input())
a = list(map(int, input().split()))

def nibeki(x):
    cnt = 0
    while(x>1):
        x //=2
        cnt += 1
    return 2**(cnt+1)

cntSet = 0
c = Counter(a)
ks = list(c.keys())
ks.sort(reverse=True)

for k in ks:
    pair = nibeki(k)-k
    if k==pair:
        cntSet += c[k]//2

    elif c[k]>0 and c[pair]>0:
        COUNT = min(c[k], c[pair])
        c[k] -= COUNT
        c[pair] -= COUNT
        cntSet +=COUNT

print(cntSet)

Solution (Python):
from collections import Counter
N, *A = map(int, open(0).read().split())
A.sort(reverse=True)
C = Counter(A)
ans = 0
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1
    partner = (2 ** (a.bit_length())) - a
    if C[partner] > 0:
        ans += 1
        C[partner] -= 1
print(ans)

Solution (Python):
from collections import Counter
N, *A = map(int, open(0).read().split())
A.sort(reverse=True)
C = Counter(A)
ans = 0
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1
    partner = (1 << (a.bit_length())) - a
    if C[partner] > 0:
        ans += 1
        C[partner] -= 1
print(ans)

Solution (Python):
import math
from collections import defaultdict
def larger_nibeki(i):
    return 2 ** len(format(i, 'b'))
N = int(input())
A = sorted(map(int, input().split()), reverse=True)
C = defaultdict(int)
for a in A:
    C[a] += 1
ans = 0
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1
    partner = larger_nibeki(a) - a
    if C[partner] > 0:
        ans += 1
        C[partner] -= 1
print(ans)

Solution (Python):
import math
from collections import defaultdict
def larger_nibeki(i):
    return 2 ** len(format(i, 'b'))
N, *A = map(int, open(0).read().split())
A.sort(reverse=True)
C = defaultdict(int)
for a in A:
    C[a] += 1
ans = 0
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1
    partner = larger_nibeki(a) - a
    if C[partner] > 0:
        ans += 1
        C[partner] -= 1
print(ans)

Solution (Python):
import math
from collections import Counter
def larger_nibeki(i):
    return 2 ** int(math.log2(a) + 1)
N, *A = map(int, open(0).read().split())
A.sort(reverse=True)
ans = 0
C = Counter(A)
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1
    partner = larger_nibeki(a) - a
    if C[partner] > 0:
        ans += 1
        C[partner] -= 1
print(ans)

Solution (Python):
import sys
fin = sys.stdin.readline
from collections import defaultdict, Counter
from bisect import bisect


possible_pows = []
cur_pow = 2
for i in range(32):
    possible_pows.append(cur_pow)
    cur_pow *= 2
assert possible_pows[-1] == 2**32


N = int(fin())
A_list = [int(elem) for elem in fin().split()]
A_list.sort(reverse=True)
rest = Counter(A_list)
num_pairs = 0
for A in A_list:
    idx = bisect(possible_pows, A)
    complement = possible_pows[idx] - A
    if rest[complement] > 0:
        if complement == A and rest[A] >= 2:
            rest[complement] -= 1
            num_pairs += 1
        elif complement != A and rest[A] >= 1:
            rest[complement] -= 1
            num_pairs += 1
    rest[A] -= 1
print(num_pairs)

Solution (Python):

from collections import Counter

N = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
b = Counter(a)

ans = 0
for t in a:
    if b[t] == 0: continue
    s = (1 << t.bit_length()) - t
    if t == s:
        ans += b[t] // 2
        b[t] %= 2
    else:
        u = min(b[s], b[t])
        ans += u
        b[s] -= u
        b[t] -= u

print(ans)

Solution (Python):

from collections import Counter

N = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
b = Counter(a)

ans = 0
for t in a:
    s = (1 << t.bit_length()) - t
    if t == s:
        ans += b[t] // 2
        b[t] %= 2
    else:
        u = min(b[s], b[t])
        ans += u
        b[s] -= u
        b[t] -= u

print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
A.sort()
pow2 = [2**i for i in range(1, 31)]
nums = []
counts = {}

for a in A:
	if a not in counts:
		nums.append(a)
		counts[a] = 0
	counts[a] += 1
nums.reverse()
ans = 0
for n in nums:
	if n not in counts:
		continue
	for p in pow2:
		if p > n and (p-n) in counts:
			if n == p - n:
				if counts[p-n] >= 2:
					ans += counts[p-n] // 2
					counts[p-n] = counts[p-n] % 2
			else:
				cnt = min(counts[p-n], counts[n])
				ans += cnt
				counts[p-n] -= cnt
				counts[n] -= cnt
print(ans)

Solution (Python):
from collections import Counter

def ans_solve(N, As):
    C = Counter(As)
    ans = 0
    for d in reversed(sorted(As)):
        n = (2 ** d.bit_length()) - d
        if d != n:
            if C[d] > 0 and C.get(n, 0) > 0:
                C[d] -= 1
                C[n] -= 1
                ans += 1
        else:
            ans += C[d]//2
            C[d] = 0
    return ans
 
 
if __name__ == "__main__":
    N = input()
    As = [int(c) for c in input().split()]
    print(ans_solve(N, As))

Solution (Python):
from collections import Counter

N = int(input())
A = list(map(int,input().split()))
ctr = Counter(A)
lctr = sorted(list(ctr.items()),reverse=True)

ans = 0
for k,_ in lctr:
    beki = 2**(len(bin(k))-2)
    a = beki-k
    if a == k:
        ans += ctr[k]//2
    else:
        tmp = min(ctr[k], ctr[a])
        ans += tmp
        ctr[a] -= tmp
print(ans)

Solution (Python):
import math
N = int(input())
A = list(map(int,input().split()))
D = {}
for i in A :
    if i in D :
        D[i] += 1
    else :
        D[i] = 1

ans = 0
A = sorted(A,reverse=True)
for i in A :
    r = 2**math.ceil(math.log2(i))
    if i == r :
        ans += (D[i] // 2)
        D[i] = 0
    else :
        b = r-i
        if D[i] > 0 and D.get(b,0) > 0 :
            D[i] -= 1
            D[b] -= 1
            ans += 1
print(ans)

Solution (Python):
import sys
import collections
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))


def solve(count):
    ret = 0
    for a in sorted(count, reverse=True):
        cnt = count[a]
        if cnt <= 0:
            continue
        maxn = 1 << a.bit_length()
        b = maxn - a
        if b in count and count[b] > 0:
            if a == b:
                c = cnt // 2
            else:
                c = min(cnt, count[b])
                count[b] -= c
            ret += c
    return ret


count_even = collections.defaultdict(lambda: 0)
count_odd = collections.defaultdict(lambda: 0)

for a in A:
    if a % 2 == 0:
        count_even[a] += 1
    else:
        count_odd[a] += 1

print(solve(count_even) + solve(count_odd))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = {}
for i in range(len(a)):
    if a[i] in b:
        b[a[i]] += 1
    else:
        b[a[i]] = 1
twins = []
now = 1
while now <= a[-1]:
    now *= 2
    twins.append(now)
for i in range(len(a) - 1, -1, -1):
    tmpa = 0
    if  b[a[i]] == 0:
        continue
    for j in range(len(twins) - 1, -1, -1):
        if twins[j] <= a[i]:
            break
        tmpa = twins[j] - a[i]
    if tmpa == a[i]:
        if b[tmpa] >= 2:
            b[tmpa] -= 2
    elif tmpa in b and b[tmpa] != 0:
        b[tmpa] -= 1
        b[a[i]] -= 1
countb = 0
for i in b:
    countb += b[i]
print((n - countb) // 2)

Solution (Python):
import bisect
 
N = int(input())
A = [int(a) for a in input().split()]
A = sorted(A)
 
c = 0
for i in range(N - 1 , -1, -1):
    if A[i] == int(A[i]):
        b = 1
        while b <= A[i]:
            b <<= 1
 
        j = bisect.bisect_left(A, b - A[i])
        if i > j:
            if b - A[i] == A[j]:
                c += 1
                A[j] = A[j] - 0.5
                A[i] = A[i] + 0.5
print(c)

Solution (Python):
from collections import defaultdict
import os, sys
if os.environ.get("USER") == "hoge":
    def debug(*args): print(*args, file=sys.stderr)
else:
    def debug(*args): pass
def debug(*args): pass
N=int(input())
A=[int(i) for i in input().split()]
dd=defaultdict(int)
for a in A:
    dd[a]+=1

B=sorted(A,reverse=True)
ans=0
for x in B:
    debug(A)
    
    if dd.get(x,-1)==0:
        continue
    s=len(bin(x))-3
    if x==1<<s:
        t=dd.get(x,-1)
        if t!=-1:
            ans+=t//2
            dd[x]-=(t//2)*2
            
            
    else:
        s+=1
        
        t=dd.get((1<<s)-x,-1)
        if t>=1:
            ans+=1
            dd[x]-=1
            dd[(1<<s)-x]-=1
            
            
print(ans)

Solution (Python):
from collections import defaultdict
import os, sys


def debug(*args): pass
N=int(input())
A=[int(i) for i in input().split()]
dd=defaultdict(int)
for a in A:
    dd[a]+=1

B=sorted(A,reverse=True)
ans=0
for x in B:
    debug(A)
    
    if dd.get(x,-1)==0:
        continue
    s=len(bin(x))-3
    if x==1<<s:
        t=dd.get(x,-1)
        if t!=-1:
            ans+=t//2
            dd[x]-=(t//2)*2
            
            
    else:
        s+=1
        
        t=dd.get((1<<s)-x,-1)
        if t>=1:
            ans+=1
            dd[x]-=1
            dd[(1<<s)-x]-=1
            
            
print(ans)

Solution (Python):
from collections import Counter
def larger_nibeki(i):
    return 2 ** len(format(i, 'b'))
N, *A = map(int, open(0).read().split())
A.sort(reverse=True)
ans = 0
C = Counter(A)
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1
    partner = larger_nibeki(a) - a
    if C[partner] > 0:
        ans += 1
        C[partner] -= 1
print(ans)