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):
from collections import Counter
from math import log2

def find(x):
    f = 2**(int(log2(x))+1)-x
    if f <= x:
        return f
    return 0

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

for i in range(n):
    f = find(a[i])
    if f == a[i]:
        m = c[a[i]]//2
    else:
        m = min(c[a[i]],c[f])
    c[a[i]] -= m
    c[f] -= m
    ans += m
print(ans)

Solution (Python):
from bisect import bisect_right
from collections import Counter

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

power = 1
powers = [1]
while power <= 10 ** 9:
    power *= 2
    powers.append(power)

a.sort()
c = Counter(a)

ans = 0
for e in a[::-1]:
    i = bisect_right(powers, e)
    target = powers[i]

    if target == 2 * e:
        if c[e] >= 2:
            c[e] -= 2
            ans += 1

    else:
        if c[e] and c[target-e]:
            c[e] -= 1
            c[target-e] -= 1
            ans += 1

print(ans)

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

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
cnt = defaultdict(int)
for a in A:
    cnt[a] += 1
n = 1
while n <= 2 * A[0]:
    n *= 2
n //= 2
ans = 0
while n > 0:
    for a in A:
        if cnt[a] == 0:
            continue
        b = n - a
        if b < 0:
            continue
        if b > a:
            break
        c = 0
        if b == a and cnt[a] > 1:
            c = cnt[a] // 2
        elif b != a and cnt[b] > 0:
            c = min(cnt[a], cnt[b])
        cnt[a] -= c
        cnt[b] -= c
        ans += c
    n //= 2
print(ans)

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
cnt = Counter(a)
ans = 0

def make(x):
    num = 1
    while num <= x:
        num *= 2
    return num

for i in range(n):
    x = make(a[i])
    if cnt[x - a[i]] > 0 and cnt[a[i]] > 0 and x != 2 * a[i]:
        ans += 1
        cnt[x - a[i]] -= 1
        cnt[a[i]] -= 1
    elif x == 2 * a[i] and cnt[a[i]] > 1:
        ans += 1
        cnt[a[i]] -= 2

print(ans)

Solution (Python):
import collections
N=int(input())
A=list(map(int,input().split()))
l=[]
c=collections.Counter(A)
values=list(c.values())	
key=list(c.keys())	
for i in range(len(key)):
    l.append([key[i],values[i]])

n=len(l)
ans=0
cnt=0
d=dict(l)

ans=0
for i in range(31,0,-1):
    piv=pow(2,i)
    cnt=0
    for j in range(n):
        val1=d.get(l[j][0])
        val2=d.get(piv-l[j][0])
        if (val1!=None)and(val2!=None):
            add=min(val1,val2)
            if l[j][0]==piv-l[j][0]:
                add=(add//2)
                ans=ans+add
                add=add*2
            else:
                ans=ans+add
            d[l[j][0]]=val1-add
            d[piv-l[j][0]]=val2-add
        
        
    
    
print(ans)

Solution (Python):
from collections import Counter
N,*A = map(int, open(0).read().split())
Cnt = Counter(A)
m = 2**31
ans = 0
for i in range(31):
  for k in Cnt.keys():
    if Cnt[k]==0:
      continue
    if k==m-k:
      ans += Cnt[k]//2
      Cnt[k] %= 2
    else:
      if Cnt[m-k]==0:
        continue
      if Cnt[k]<Cnt[m-k]:
        ans += Cnt[k]
        Cnt[m-k] -= Cnt[k]
        Cnt[k] = 0
      else:
        ans += Cnt[m-k]
        Cnt[k] -= Cnt[m-k]
        Cnt[m-k] = 0
  m >>= 1
print(ans)

Solution (Python):
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
a=0
for i in range(30,0,-1):
    t=2**i
    if t//2 in d:
        a+=d[t//2]//2
        if d[t//2]%2:
            d[t//2]=1
        else:
            d.pop(t//2)
    for n,v in d.items():
        if n>=t//2:
            continue
        if t-n in d:
            w=d[t-n]
            if v>w:
                a+=w
                d[n]=v-w
                d[t-n]=0
            else:
                a+=v
                d[t-n]=w-v
                d[n]=0    
print(a)

Solution (Python):
from collections import defaultdict

def twosum(n):
  now = 1
  while n >= now:
    now *= 2
  return now - n
n=int(input())
a=sorted(list(map(int,input().split())))
d = defaultdict(int)
for i in a:
    d[i] += 1
ans = 0
for i in a[::-1]:
    find = twosum(i)
    if d[i] <= 0:
        continue
    d[i] -= 1
    if d[find] <= 0:
        d[i] += 1
    else:
        ans += 1
        d[find] -= 1
print(ans)

Solution (Python):
from collections import defaultdict

def twosum(n):
  now = 1
  while n >= now:
    now *= 2
  return now - n
n=int(input())
a=sorted(list(map(int,input().split())))
d = defaultdict(int)
for i in a:
    d[i] += 1
ans = 0
for i in a[::-1]:
    d[i] -= 1
    find = twosum(i)
    if d[find] > 0 and d[i] >= 0:
        ans += 1
        d[find] -= 1
    else:
        d[i] += 1
print(ans)

Solution (Python):
from collections import Counter
n=int(input())
a=sorted(list(map(int,input().split())),reverse=1)
b=Counter(a)
cnt=0
for i in range(n):
    if b[a[i]]<=0:
        continue
    k=a[i].bit_length()
    x=(1<<k)-a[i]
    if x==a[i]:
        if b[x]>1:
            cnt+=1
            b[x]-=2
    elif x in b and b[x]>0:
        cnt+=1
        b[a[i]]-=1
        b[x]-=1
print(cnt)

Solution (Python):
from collections import defaultdict

def twosum(n):
  now = 1
  while n >= now:
    now *= 2
  return now - n
n = int(input())
a = sorted(list(map(int, input().split())))
d = defaultdict(int)
for i in a:
  d[i] += 1
ans = 0
for i in a[::-1]:
  d[i] -= 1
  find = twosum(i)
  if d[find] > 0 and d[i] >= 0:
    ans += 1
    d[find] -= 1
  else:
    d[i] += 1
print(ans)

Solution (Python):
import sys
from bisect import bisect_right
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    _ = int(rl())
    A = list(map(int, rl().split()))
    
    pow_of_2 = [1]
    while pow_of_2[-1] < 2 * 10 ** 9:
        pow_of_2.append(pow_of_2[-1] * 2)
    
    A.sort(reverse=True)
    counter = defaultdict(int)
    for ai in A:
        counter[ai] += 1
    
    ans = 0
    for ai in A:
        if counter[ai] == 0:
            continue
        idx = bisect_right(pow_of_2, 2 * ai) - 1
        t = pow_of_2[idx]
        aj = t - ai
        if 1 < counter[aj] or 0 < counter[aj] and ai != aj:
            ans += 1
            counter[ai] -= 1
            counter[aj] -= 1
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
from collections import Counter

def get_smallest_power_of_2_over_N(N):
    i=2
    while i<=N:
        i*=2
    return i

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


A = sorted(A)

ans=0
D=Counter(A)

for i in reversed(range(N)):
    pair_val = get_smallest_power_of_2_over_N(A[i]) - A[i]
    if D[A[i]]<=0:
        continue
    elif pair_val==A[i] and D[pair_val]>=2 or pair_val!=A[i] and  D[pair_val]>=1:
        ans+=1
        D[pair_val]-=1
        D[A[i]]-=1

print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = sorted(LI())
cnt = Counter(A)
ans = 0
for i in range(n - 1, -1, -1):
    a = A[i]
    if cnt[a]:
        cnt[a] -= 1
        b = 2 ** a.bit_length() - a
        if cnt[b]:
            ans += 1
            cnt[b] -= 1

print(ans)

Solution (Python):
from collections import Counter

N = int(input())
*A, = map(int, input().split())
cnt = Counter(A)
A = sorted(A, reverse=True)
ans = 0
for a in A:
    if a & (a - 1) != 0:
        cand = (1 << ((a - 1).bit_length())) - a
        if cnt[a] == 0 or cnt[cand] == 0: continue
    else:
        cand = a
        if cnt[a] < 2: continue
    ans += 1
    cnt[a] -= 1; cnt[cand] -= 1
print(ans)

Solution (Python):
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import heapq

n = ni()
a = na()
ls = []

for i in a:
    heapq.heappush(ls,-i)

s = {}
ans = 0

for _ in range(n):
    m = -heapq.heappop(ls)
    if m in s and s[m] > 0:
        s[m] -= 1
        ans += 1
        continue
    dif = 2**m.bit_length()-m
    if dif in s:
        s[dif] += 1
    else:
        s[dif] = 1

print(ans)

Solution (Python):
import bisect
N=int(input())
alist=list(map(int,input().split()))
alist.sort(reverse=True)

blist=[]
for a in alist:
  a2=a
  digit_a2=0
  while(a2>0):
    a2>>=1
    digit_a2+=1
  b=2**(digit_a2)-a
  blist.append(b)



dic_a={}
for a in alist:
  if a in dic_a:
    dic_a[a]+=1
  else:
    dic_a[a]=1

answer=0
for i in range(N):
  a=alist[i]
  b=blist[i]
  if a==b:
    if dic_a[a]>1:
      dic_a[a]-=2
      answer+=1
      
  else:
    if dic_a[a]>0 and b in dic_a and dic_a[b]>0:
      dic_a[a]-=1
      dic_a[b]-=1
      answer+=1
      
    
print(answer)

Solution (Python):
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
A.sort()
C = Counter(A)
ans = 0
for i in range(n-1,-1,-1):
    temp = A[i]
    beki = 1
    if C[temp] == 0:
        continue
    while beki <= temp:
        beki *= 2
    counterpart = beki-temp
    if C[counterpart] > 0 and C[temp] > 0 and counterpart != temp:
        C[counterpart] -= 1
        C[temp] -= 1
        ans += 1
    elif counterpart == temp and C[counterpart] > 1:
        C[counterpart] -= 2
        ans += 1
print(ans)

Solution (Python):
import bisect
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
A.sort()
C = Counter(A)
ans = 0
for i in range(n-1,-1,-1):
    temp = A[i]
    beki = 1
    while beki <= temp:
        beki *= 2
    counterpart = beki-temp
    if C[counterpart] > 0 and C[temp] > 0 and counterpart != temp:
        C[counterpart] -= 1
        C[temp] -= 1
        ans += 1
    elif counterpart == temp and C[counterpart] > 1:
        C[counterpart] -= 2
        ans += 1
print(ans)

Solution (Python):
from bisect import *
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
A.sort()
C = Counter(A)
ans = 0
for i in range(N):
    a = A[N-i-1]
    if C[a] == 0:
        continue
    b = pow(2, a.bit_length())
    if C[b-a]-((a<<1) == b) > 0:
        C[a] -= 1
        C[b-a] -= 1
        ans += 1
print(ans)

Solution (Python):
from collections import defaultdict
import heapq

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

data=defaultdict(int)
for i in range(0,N):
    data[A[i]]+=1

A=[-A[i] for i in range(0,N)]
heapq.heapify(A)
count=0
while A:
    x=-heapq.heappop(A)
    if data[x]!=0:
        data[x]-=1
        y=2**(len(bin(x))-2)-x
        if data[y]!=0:
            data[y]-=1
            count+=1

print(count)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    n = II()
    a = LI()
    a.sort()
    d = defaultdict(int)
    for ai in a:
        d[ai] += 1
    ans = 0
    for j in range(n - 1, -1, -1):
        i = 0
        aj = a[j]
        while aj:
            aj >>= 1
            i += 1
        m = 1 << i
        if d[a[j]]:
            if m - a[j] == a[j]:
                x = d[a[j]]
                d[a[j]] -= x
                ans += x // 2
            else:
                x = m - a[j]
                if bisect_right(a, x) - bisect_left(a, x) and d[x]:
                    x = d[a[j]]
                    y = d[m - a[j]]
                    d[a[j]] -= min(x, y)
                    d[m - a[j]] -= min(x, y)
                    ans += min(x, y)

    print(ans)

    return



if __name__ == '__main__':
    solve()

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
count = Counter(a)
a.sort(reverse=True)
ans = 0
for num in a:
    if count[num] == 0:
        continue
    else:
        
        p = 2 ** num.bit_length()
        if p - num == num:
            if count[p - num] > 1:
                sub = count[num] // 2
                ans += sub
                count[num] -= sub * 2
        else:
            if count[p - num] > 0:
                sub = min(count[p - num], count[num])
                ans += sub
                count[p-num] -= sub
                count[num] -= sub
print(ans)

Solution (Python):
from collections import Counter

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

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

ans = 0
for a in A:
    if not cnt[a]: continue

    
    p = 2 ** a.bit_length()
    if cnt[p - a]:
        if a == p - a:
            if cnt[a] >= 2:
                ans += 1
                cnt[a] -= 2
        else:
            ans += 1
            cnt[p - a] -= 1
            cnt[a] -= 1

print(ans)

Solution (Python):



from collections import defaultdict

N = int(input())
As = sorted(list(map(int, input().split())),reverse=True)
d = defaultdict(int)
for a in As:
    d[a] += 1

cnt = 0
for a in As:
    if d[a] == 0:continue
    d[a] -= 1
    n = 0
    while 2**n <= a:
        n += 1
    p = 2**n - a
    if d[p] > 0:
        cnt += 1
        d[p] -= 1

print(cnt)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

def f(x):
    pow_2 = 1
    while pow_2 <= x:
        pow_2*=2
    return pow_2-x
def main():
    N=I()
    A=sorted(LI())
    C = Counter(A)
    ans = 0
    for a in A[::-1]:
        pair = f(a)

        if(a!=pair and C[a] and C[pair]):
            ans += 1
            C[a]-=1
            C[pair]-=1
        if(a==pair and C[a]>=2):
            ans += 1
            C[a]-=2
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    d = {}
    for i in A:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    r = 0
    for i in A:
        if d[i] == 0:
            continue
        for j in reversed(range(1,32)):
            t = pow(2, j) - i
            if t == i:
                if d[t] > 1:
                    d[t] -= 2
                    r += 1
            elif t in d and d[t] > 0:
                d[t] -= 1
                d[i] -= 1
                r += 1
    return r
print(main())

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
import collections
d=collections.defaultdict(int)
for i in l:
    d[i]+=1
l.sort(reverse=True)
ans=0
for i in l:
    if d[i]>0:
        d[i]-=1
        if d[2**i.bit_length()-i]>0:
            ans+=1
            d[2**i.bit_length()-i]-=1
print(ans)

Solution (Python):
from bisect import bisect_left
from bisect import bisect_right

n = int(input())
a = [int(x) for x in input().split()]
a = sorted(a)

ans = 0
visited = [False]*n

while a:
    s = a.pop()
    if visited.pop():
        continue
    m = 1
    while m <= s:
        m *= 2
    r = bisect_right(a, m-s)
    l = bisect_left(a, m-s)
    for x in range(l, r)[::-1]:
        if not visited[x]:
            visited[x] = True
            ans += 1
            break

print(ans)

Solution (Python):
from collections import Counter

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

ans = 0

while A:
    a = A.pop()
    if cnt[a] <= 0:
        continue
    cnt[a] -= 1
    pair = (1 << a.bit_length()) - a
    if cnt[pair] > 0:
        ans += 1
        cnt[pair] -= 1

print(ans)

Solution (Python):
def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

    _ = int(input())
    A = [int(i) for i in input().split()]

    ans = 0
    c = Counter(A)
    B = sorted(c.keys(), reverse=True)

    for b in B:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            if a in c:
                cur = min(c[a], c[b])
            else:
                cur = 0
        ans += cur
        
        c[a] -= cur

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

    _ = int(input())
    A = [int(i) for i in input().split()]

    ans = 0
    c = Counter(A)
    B = sorted(c.keys(), reverse=True)

    for b in B:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            if a in c:
                cur = min(c[a], c[b])
            else:
                cur = 0
        ans += cur
        
        c[a] -= cur

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

    _ = int(input())
    A = [int(i) for i in input().split()]

    ans = 0
    c = Counter(A)
    B = sorted(c.keys(), reverse=True)

    for b in B:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            if a in c.keys():
                cur = min(c[a], c[b])
            else:
                cur = 0
        ans += cur
        
        c[a] -= cur

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

    _ = int(input())
    A = [int(i) for i in input().split()]

    ans = 0
    c = Counter(A)
    B = sorted(c.keys(), reverse=True)

    for b in B:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            if a in c:
                cur = min(c[a], c[b])
            else:
                cur = 0
        ans += cur
        
        c[a] -= cur

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

    _ = int(input())
    A = [int(i) for i in input().split()]

    ans = 0
    c = Counter(A)
    B = sorted(c.keys(), reverse=True)
    
    for b in B:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            if a in c:
                cur = min(c[a], c[b])
            else:
                cur = 0
        ans += cur
        
        c[a] -= cur

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

    _ = int(input())
    A = [int(i) for i in input().split()]

    ans = 0
    c = Counter(A)
    B = sorted(c.keys(), reverse=True)

    for b in B:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            cur = min(c[a], c[b])
        ans += cur
        
        c[a] -= cur

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

    _ = int(input())
    A = [int(i) for i in input().split()]

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

    for b in A:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            cur = min(c[a], c[b])
        ans += cur
        c[b] -= cur
        c[a] -= cur
        

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

    _ = int(input())
    A = [int(i) for i in input().split()]

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

    for b in A:
        if c[b] == 0:
            continue
        a = (2 ** b.bit_length()) - b
        if a == b:
            cur = c[b]//2
        else:
            cur = min(c[a], c[b])
        ans += cur
        c[b] -= cur
        c[a] -= cur
        

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))

    ans = 0
    A.sort(reverse=True)
    C = Counter(A)
    for a in A:
        if C[a] == 0: continue
        C[a] -= 1
        p = (1 << a.bit_length()) - a
        if p > a: continue
        if p in C and C[p] > 0:
            ans += 1
            C[p] -= 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    A.sort()
    nDict = dict()
    for i, a in enumerate(A):
        if a in nDict: nDict[a] += 1
        else: nDict[a] = 1

    count = 0
    for i in reversed(range(N)):
        if nDict[A[i]] == 0: continue
        k = 1
        while k <= A[i]: k <<= 1
        if k - A[i] in nDict:
            if k - A[i] == A[i] and nDict[k - A[i]] > 1:
                count += 1
                nDict[A[i]] -= 2
            elif k - A[i] != A[i] and nDict[k - A[i]] > 0:
                count += 1
                nDict[A[i]] -= 1
                nDict[k - A[i]] -= 1
    print(count)
        

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
from collections import Counter
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))

    ans = 0
    A.sort(reverse=True)
    C = Counter(A)
    for a in A:
        if C[a] == 0: continue
        C[a] -= 1
        p = (1 << a.bit_length()) - a
        if p in C and C[p] > 0:
            ans += 1
            C[p] -= 1
    print(ans)

if __name__ == '__main__':
    main()

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

ans = 0
for k in range(N-1,-1,-1):
    t = A[k]
    for d in range(1,32):
        if A[0] <= 2**d - t <= A[k]:
            i = bisect.bisect_left(A,2**d-t)
            if A[i] == 2**d-t and k != i:
                ans += 1
                A[k] += 0.01
                A[i] -= 0.01

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 i in a:
  if c[i]==0:
    continue
  pt=2**len(format(i,'b'))
  c[i]-=1
  if c[pt-i]>=1:
    ans+=1
    c[pt-i]-=1
print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
from collections import Counter
c=Counter(a)
ans=0
for i in a:
  if c[i]==0:continue
  m=1<<i.bit_length()
  c[i]-=1
  if c[m-i]:
    ans+=1
    c[m-i]-=1
print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
from collections import Counter
c=Counter(a)
ans=0
for i in a:
  if c[i]==0:continue
  m=1<<i.bit_length()
  c[i]-=1
  if c[m-i]:
    ans+=1
    c[m-i]-=1
print(ans)

Solution (Python):
from collections import Counter

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

ans = 0
while A:
    a = A.pop()
    if c[a] <= 0:
        continue
    c[a] -= 1
    Num = 1 << (a.bit_length())
    cand = Num - a  
    if c[cand] > 0:
        ans += 1
        c[cand] -= 1

print(ans)

Solution (Python):
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline

N, *A = map(int, read().split())

A.sort()
a = Counter(A)
answer = 0


while A:
    n = A.pop()
    if a[n] == 0:
        continue

    a[n] -= 1
    
    s = 1 << (2 * n).bit_length()
    while n < s:
        b = s - n
        if a[b] > 0:
            answer += 1
            a[b] -= 1
            break
        s //= 2

print(answer)

Solution (Python):
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline

N, *A = map(int, read().split())

A.sort()
a = Counter(A)
answer = 0

limit = 1 << ((2 * 10 ** 9 + 1).bit_length() - 1)

while A:
    n = A.pop()
    if a[n] == 0:
        continue

    a[n] -= 1
    s = limit
    while n < s:
        b = s - n
        if a[b] > 0:
            answer += 1
            a[b] -= 1
            break
        s //= 2

print(answer)

Solution (Python):
from collections import Counter

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

C = Counter(A)
count = 0

for i in range(N):
    while C[A[i]]:
        C[A[i]] -= 1
        if C[2**(A[i].bit_length()) - A[i]]:
            C[2**(A[i].bit_length()) - A[i]] -= 1
            count += 1

print(count)

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

import bisect
n = inn()
a = inl()
done = [False]*n
ofs = [0]*n
cnt = 0
a.sort()
for i in range(n-1,0,-1):
    if done[i]:
        continue
    for j in range(32):
        if 2**j>a[i]:
            break
    x = 2**j-a[i]
    j = bisect.bisect_left(a,x)
    if j>=i:
        continue
    k = j+ofs[j]
    if k<i and a[k]==x:
        done[k] = done[i] = True
        ofs[j] += 1
        cnt += 1
print(cnt)

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

n = int(input())
A = sorted(map(int, input().split()), reverse=True)
C = Counter(A)
ans = 0
for a in A:
  if not C[a]:
    continue
  r = (1<<a.bit_length()) - a
  if r != a:
    if r in C and C[r] > 0:
      ans += 1
      C[r] -= 1
  else:
    if C[r] >= 2:
      ans += 1
      C[r] -= 1
  C[a] -= 1
print(ans)

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

n = int(input())
A = sorted(map(int, input().split()), reverse=True)
C = Counter(A)
ans = 0
for a in A:
  if not C[a]:
    continue
  r = (1<<a.bit_length()) - a
  if r != a:
    if r in C and C[r] > 0:
      ans += 1
      C[r] -= 1
  else:
    if C[r] >= 2:
      ans += 1
      C[r] -= 1
  C[a] -= 1
print(ans)

Solution (Python):

N = int(input())

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

"""

2べきになる条件は？
→片方が2の補数であること

Nが大きい→貪欲的に
最大の奴はそれより小さい奴としかペアを組めない
→大きい奴から貪欲にとっけいけばいける？

いけそうかなぁ
"""

A.sort()
dic = {}
lis = []

for i in range(N):
    
    if i == 0 or A[i-1] != A[i]:
        dic[A[i]] = 1
        lis.append(A[i])
    else:
        dic[A[i]] += 1

lis.reverse()
ans = 0
d2lis = {}
for i in range(32):
    d2lis[2**i] = i

import math

for i in lis:

    if i in d2lis:
        ans += dic[i]//2
        dic[i] %= 2
    else:
        t = 2 ** (int(math.log(i,2)) + 1)
        if t-i in dic:
            ans += min(dic[i],dic[t-i])
            dic[t-i] = max(0, dic[t-i]-dic[i])

print (ans)

Solution (Python):
from collections import defaultdict
N, *A = map(int, open(0).read().split())
ans = 0
A.sort()
dic = defaultdict(list)
for i, a in enumerate(A):
  dic[a] += [i]
for i in range(N-1,-1,-1):
  a = A[i]
  if dic[a]==[]:
    continue
  dic[a].pop()
  k = 1
  while k<=a:
    k *= 2
  n = k-a
  if dic[n]!=[]:
    dic[n].pop()
    ans += 1
print(ans)

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]

dic = {}
for a in A:
    if a in dic:
        dic[a] += 1
    else:
        dic[a] = 1
        
A.sort(reverse=True)
ans = 0
for a in A:
    if dic[a] == 0:
        continue
    dic[a] -= 1
    num = pow(2, len(bin(a))-2) - a
    if num in dic and dic[num] > 0:
        ans += 1
        dic[num] -= 1

print(ans)

Solution (Python):
from collections import Counter

def main():
    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:
            k = (1 << a.bit_length()) - a
            if k in C and C[k] != 0 and not (k == a and C[a] == 1):
                ans += 1
                C[a] -= 1
                C[k] -= 1
    print(ans)

if __name__ == "__main__":
    main()