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 defaultdict
import bisect

N = int(input())
A = list(map(int, input().split()))
L2 = [1]
for i in range(40):
    L2.append(L2[-1]*2)
D = defaultdict(int)
for a in A:
    D[a] += 1
A.sort(reverse=True)
res = 0
for a in A:
    if D[a] < 1:
        continue
    D[a] -= 1
    beki2 = L2[bisect.bisect_right(L2, a)]
    j = beki2 - a
    if D[j] > 0:
        D[j] -= 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)
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):
from itertools import *
import copy
from collections import *


N=int(input())
A=list(map(int,input().split()))
idle_max=10**9
peki2=[]
for i in range(1,100):
    a=2**i
    if a<=2*idle_max:
        peki2.append(a)
peki2.sort(reverse=True)
lst=[[],[]]
for a in A:
    if a%2:
        lst[1].append(a)
    else:
        lst[0].append(a)

lst[0].sort(reverse=True)
lst[1].sort(reverse=True)
setlst=[set(lst[0]),set(lst[1])]
Counerlst=[Counter(lst[0]),Counter(lst[1])]

count=0
for l in range(2):
    for n in lst[l]:
        if n in setlst[l]:
            for p in peki2:
                a=p-n

                if a in setlst[l]:
                    if n==a:
                        if Counerlst[l][n]>=2:
                            count+=1
                            Counerlst[l][n]-=2
                            if Counerlst[l][n]==0:
                                setlst[l].remove(n)
                    else:

                        count+=1
                        Counerlst[l][a]-=1
                        Counerlst[l][n]-=1
                        if Counerlst[l][a]==0:
                            setlst[l].remove(a)
                        if Counerlst[l][n]==0:
                            setlst[l].remove(n)
                    break
print(count)

Solution (Python):
from collections import Counter
if __name__ == "__main__":
    N=int(input())
    lista=list(map(int,input().split()))
    mii=Counter(lista)
    si=set(lista)
    listb=[i for i in si]
    listb.sort()
    ans=0
    while(len(listb)>0):
        x=listb.pop()
        if mii[x]>0:
            k=1
            while k<=x:
                k*=2
            y=k-x
            if x==y:
                ans+=mii[x]//2
            elif y<x and y in si:
                m=min(mii[x],mii[y])
                ans+=m
                mii[y]-=m
            mii[x]=0
    print(ans)

Solution (Python):
from math import log2, ceil
from collections import defaultdict

N = int(input())
A = sorted(list(map(int, input().split())))[::-1]

cnt = defaultdict(int)
for a in A:
  cnt[a] += 1

answer = 0
for a in A:
  if cnt[a]:
    if ceil(log2(a)) == log2(a):
      i = (1 << (ceil(log2(a)) + 1)) - a
    else:
      i = (1 << ceil(log2(a))) - a

    if i != a:
      if cnt[i]:
        cnt[a] -= 1
        cnt[i] -= 1
        answer += 1
    else:
      if cnt[i] > 1:
        cnt[a] -= 2
        answer += 1
        
print(answer)

Solution (Python):
from bisect import bisect_left
N = int(input())
A = sorted(list(map(int,input().split())))
A = [[A[i],0] for i in range(N)]
cnt = 0
for i in range(N-1,0,-1):
    if A[i][1]==0:
        a = A[i][0]
        A[i][1]=1
        k = 0
        while 2**k<=a:
            k += 1
        b = 2**k-a
        ind = bisect_left(A,[b,1])
        ind -= 1
        if ind<i and A[ind]==[b,0]:
            A[ind][1]=1
            cnt += 1
print(cnt)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
import math
import collections
powers =[2**i for i in range(1,int(math.log(max(A),2)+2))]
table=collections.defaultdict(int)
table2=collections.defaultdict(set)
ans=0
for i in range(N):
  table[A[i]]+=1
for x in table:
  for y in reversed(powers):
    if y - x in table:
      table2[x].add(y-x)
        
        
        
table2 =list(table2.items())
table2.sort(key = lambda x:len(x[1]))

for x,y in table2:
  while(table[x]>0):
    table[x]-=1
    for z in y:
      if table[z]>0:
        ans+=1
        table[z]-=1
        break
print(ans)

Solution (Python):
from math import log2
import heapq as hq
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
a = [-a[i] for i in range(n)]
hq.heapify(a)
ans = 0
while a:
  x = hq.heappop(a)
  x = -x
  if c[x]>0:
    y = 2**(int(log2(x))+1)
    if x*2 == y:
      ans += c[x]//2
      c[x] = c[x]%2
    else:
      if c[y-x]>0:
        ans += 1
        c[x] -= 1
        c[y-x] -= 1
print(ans)

Solution (Python):
from collections import Counter
size_a = int(input())
a = Counter(int(x) for x in input().split())
keys = list(a.keys())
keys.sort()
pair_cnt = 0
while size_a >= 2:
    x = keys[-1]
    if a[x] == 0:
        keys.pop()
        continue
    a[x] -= 1
    size_a -= 1
    if a[x] == 0:
        keys.pop()
    b = 2 ** x.bit_length() - x
    if a[b] > 0:
        a[b] -= 1
        size_a -= 1
        if a[b] == 0:
            del a[b]
        pair_cnt += 1
print(pair_cnt)

Solution (Python):
from collections import Counter

N = int(input())
A = sorted([int(x) for x in input().split()], reverse=True)
C = Counter(A)

ans = 0
for a in A:
    if C[a] == 0:
        continue
    pt = 2 ** len(format(a, 'b'))
    C[a] -= 1
    if C[pt - a] >= 1:
        C[pt - a] -= 1
        ans += 1
print(ans)

Solution (Python):


import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

C = Counter(A)
ans = 0

for i in range(30, 0, -1):
    x = 2 ** i
    for k in C.keys():
        if x-k in C:
            
            if k == x-k:
                p = C[k] // 2
                C[k] -= p * 2
                ans += p
            else:
                
                p = min(C[k], C[x-k])
                C[k] -= p
                C[x-k] -= p
                ans += p
print(ans)

Solution (Python):


import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

C = Counter(A)
ans = 0

for i in range(30, 0, -1):
    x = 2 ** i
    for k in C.keys():
        if x-k in C:
            
            if k == x-k:
                p = C[k] // 2
                C[k] -= p * 2
                ans += p
            else:
                
                p = min(C[k], C[x-k])
                C[k] -= p
                C[x-k] -= p
                ans += p
print(ans)

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

def main():
    N = int(input())
    A = list(map(int,input().split()))
    d = defaultdict(int)
    for x in A:
        d[x] += 1
    A = list(set(A))
    A.sort(reverse = True)
    l = len(A)
    
    def exp(x):
        l = len(str(bin(x))[2:])
        return 2**l

    ans = 0
    for i in range(l):
        a = A[i]
        if exp(a)//2 == a:
            ans += int(d[a]//2)
        else:
            m = min(d[a],d[exp(a)-a])
            ans += m
            d[a] -= m
            d[exp(a)-a] -= m
            
    print(ans)
    
if __name__ == "__main__":
    main()

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

def main():
    N = int(input())
    A = list(map(int,input().split()))
    d = defaultdict(int)
    for x in A:
        d[x] += 1
    A = list(set(A))
    A.sort(reverse = True)
    l = len(A)
    
    def exp(x):
        l = len(str(bin(x))[2:])
        return 2**l

    ans = 0
    for i in range(l):
        a = A[i]
        if exp(a)//2 == a:
            ans += int(d[a]//2)
        else:
            m = min(d[a],d[exp(a)-a])
            ans += m
            d[a] -= m
            d[exp(a)-a] -= m
            
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
ball = list(map(int, input().split()))
ball.sort(reverse = True)
ok = {}
for x in ball:
    if x in ok:
        ok[x] += 1
    else:
        ok[x] = 1
ans = 0
for x in ball:
    if ok[x] != 0:
        y = 2**(x.bit_length()) - x
        if y in ok:
            if ok[y] != 0:
                if y == x and ok[y] == 1: 
                    continue
                ans += 1
                ok[x] -= 1
                ok[y] -= 1
print(ans)

Solution (Python):
def examA():
    S = SI()
    cur = 0; ans = 0
    for i,s in enumerate(S):
        if s=="W":
            ans += i-cur
            cur +=1
    print(ans)
    return

def examB():
    N = I()
    A = LI(); A.sort(reverse = True)
    ans = 0
    c = Counter(A)
    for a in A:
        cur = (1 << a.bit_length()) - a
        if c[a]>0 and c[cur]>0:
            if a==cur:
                ans += c[a]//2
                c[a]=0
                continue
            n = min(c[a],c[cur])
            c[a] -= n; c[cur] -= n
            ans += n

    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examB()

Solution (Python):
from bisect import bisect_left
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
A.sort()
t=0
for i in range(N):
    while 2**t<=A[i]:
        if 2**t<=A[i]<2**(t+1):
            break
        t+=1
    B[i]=2**(t+1)-A[i]
i=N-1
count=0
flag=[0]*N
for i in range(N-1,0,-1):
    if flag[i]==1:
        continue
    flag[i]=1
    b=bisect_left(A,B[i])
    if A[b]==B[i] and flag[b]==0:
        flag[i]=1
        flag[b]=1
        A[b]-=1
        count+=1
print(count)

Solution (Python):
import sys
from collections import Counter

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

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  
rs = lambda: stdin.readline().rstrip()  

N = ri()
A = rl()
A.sort(reverse=True)
c = Counter(A)
answer = 0
for x in A:
    target = (1 << x.bit_length()) - x
    while c[x] > 0:
        c[x] -= 1
        if c[target] > 0:
            c[target] -= 1
            answer += 1

print(answer)

Solution (Python):
import sys
from collections import Counter

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

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  
rs = lambda: stdin.readline().rstrip()  

N = ri()
A = rl()
A.sort(reverse=True)
c = Counter(A)
answer = 0
for x in A:
    target = (1 << x.bit_length()) - x
    while c[x] > 0:
        c[x] -= 1
        if c[target] > 0:
            c[target] -= 1
            answer += 1

print(answer)

Solution (Python):
import bisect
from collections import Counter

power2 = [1]
while power2[-1] < 10**9:
    power2.append(power2[-1]*2)

N = int(input())
A = sorted([int(i) for i in input().split()], reverse=True)
C = Counter(A)

ans = 0
for a in A:
    if C[a] == 0:
        continue
    C[a] -= 1

    i = bisect.bisect_right(power2, a)
    if C[power2[i]-a] >= 1:
        ans += 1
        C[power2[i]-a] -= 1

print(ans)

Solution (Python):
from bisect import bisect_left
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
A.sort()
t=0
for i in range(N):
    while 2**t<=A[i]:
        if 2**t<=A[i]<2**(t+1):
            break
        t+=1
    B[i]=2**(t+1)-A[i]
i=N-1
count=0
flag=[0]*N
for i in range(N-1,0,-1):
    if flag[i]==1:
        continue
    flag[i]=1
    b=bisect_left(A,B[i])
    if A[b]==B[i] and flag[b]==0:
        flag[i]=1
        flag[b]=1
        A[b]-=1
        count+=1
print(count)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



from bisect import bisect_left

N = I()
A = III()
A.sort()

val = []
num = []
before = 0
for a in A:
    if a != before:
        val.append(a)
        num.append(1)
        before = a
    else:
        num[-1] += 1

ans = 0

for i in range(N)[::-1]:
    s = math.floor(math.log(2*A[i],2))
    p = bisect_left(val,2**s-A[i])
    if A[i]==2**s-A[i]:
        if num[p]>=2:
            ans += 1
            num[p] -= 2
    else:
        j = bisect_left(val,A[i])
        if p<=len(val)-1:
            if val[p]==2**s-A[i] and num[j] and num[p]:
                ans += 1
                num[j] -= 1
                num[p] -= 1

print(ans)

Solution (Python):
import math
import bisect
import collections

N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)
A = sorted(list(C.keys()))



ans = 0
for i in range(len(A)-1,-1,-1):
  a = A[i]
  b = (1<<(int(math.log(a,2))+1))-a
  if a == b:
    ans += C[a]//2
    C[a] -= C[a]//2*2
  else:
    r = bisect.bisect_left(A, b)
    if r < i and A[r] == b:
      mn = min(C[a],C[A[r]])
      ans += mn
      C[a] -=  mn
      C[A[r]] -= mn
print(ans)

Solution (Python):
import math
n = int(input())
l = sorted(list(map(int,input().split())))
c = 0
b = {}
for i in range(len(l)):
    if l[i] in b:
        b[l[i]] += 1
    else:
        b[l[i]] = 1

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    D=defaultdict(int)
    for a in A:
        D[a]+=1

    A.sort(reverse=1)
    ans=0
    for a in A:
        if(D[a]==0): continue
        k=a.bit_length()
        d=(1<<k)-a
        if(a!=d):
            if(D[d]):
                ans+=1
                D[a]-=1
                D[d]-=1
        else:
            if(D[d]>=2):
                ans+=1
                D[d]-=2
    print(ans)
resolve()

Solution (Python):
from collections import*
n,*a=map(int,open(0).read().split())
C=Counter(a)
r=0
for x in sorted(a)[::-1]:
	if C[x]>0:y=1<<x.bit_length();C[x]-=1;r+=C[y-x]>0;C[y-x]-=1
print(r)

Solution (Python):
from collections import Counter
n, *a = map(int, open(0).read().split())
C = Counter(a)
ans = 0
for x in sorted(a)[::-1]:
	if not C[x]:
		continue
	y = 1 << x.bit_length()
	C[x] -= 1
	if C[y - x]:
		ans += 1
		C[y - x] -= 1
print(ans)

Solution (Python):
def upper_pow2(n):
    ret = 1
    while n > 0:
        ret <<= 1
        n >>= 1
    return ret


n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
d = dict()
for x in a:
    if x in d:
        d[x] += 1
    else:
        d[x] = 1
ans = 0
for x in a:
    if d[x] <= 0:
        continue
    if x & (x - 1):
        t = upper_pow2(x) - x
        if t in d and d[t] > 0:
            d[x] -= 1
            d[t] -= 1
            ans += 1
    else:
        if d[x] >= 2:
            d[x] -= 2
            ans += 1
print(ans)

Solution (Python):
def main():
    from bisect import bisect_right as br
    from collections import Counter as ct
    check=[]
    i=1
    while i<=10**10:
        check.append(i)
        i*=2
    n=int(input())
    c=ct(list(map(int,input().split())))
    c_l=sorted(list(c.keys()),reverse=True)
    ans=0
    for i in c_l:
        j=check[br(check,i)]-i
        if i==j:
            ans+=c[i]//2
        else:
            ans+=min(c[i],c[j])
            c[j]-=min(c[i],c[j])
    print(ans)
main()

Solution (Python):
from collections import Counter
N = int(input())
A = [int(i) for i in input().split()]

c = Counter(A)
b = sorted(c.keys())

ret = 0
for j in range(len(c) - 1, -1, -1) :
    i = 2
    while c[b[j]] > 0 and i - b[j] <= b[j] :
        if b[j] != i - b[j] :
            if c[b[j]] > 0 and c[i-b[j]] > 0 :
                M = min(c[b[j]], c[i-b[j]])
                ret += M
                c[b[j]] -= M
                c[i-b[j]] -= M
        else :
            if c[b[j]] > 1 :
                ret += c[b[j]] // 2
                c[b[j]] %= 2
        i *= 2
    
print(ret)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    bp = list(reversed([2**i for i in range(2, 32)]))
    C = Counter(A)
    ans = 0
    A.sort(reverse=True)
    for k in A:
        if C[k] <= 0:
            continue
        C[k] -= 1
        r = (1 << k.bit_length()) - k
        if C[r] > 0:
            ans += 1
            C[r] -= 1

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    
    
    
    


if __name__ == '__main__':
    main()

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

x=a[0];ctn=1;l=[];l2=[]
for i in range(1,n):
  if x==a[i]:
    ctn+=1
  else:
    l.append([x,ctn])
    l2.append(x)
    x=a[i]
    ctn=1
l.append([x,ctn])
l2.append(x)

b=[2**i for i in range(1,50)]

ct=0
for i in range(len(l2)-1,-1,-1):
  x=math.floor(math.log2(l2[i]))
  x=b[x]-l2[i]
  y=bisect.bisect_left(l2,x)
  if l2[y]==x:
    if l2[y]!=l2[i]:
      m=min(l[i][1],l[y][1])
    else:
      m=l[i][1]//2
    l[i][1]-=m
    l[y][1]-=m
    ct+=m
print(ct)

Solution (Python):
import math
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
x=a[0]
ctn=1
l=[]
l2=[]
for i in range(1,n):
  if x==a[i]:
    ctn+=1
  else:
    l.append([x,ctn])
    l2.append(x)
    x=a[i]
    ctn=1
l.append([x,ctn])
l2.append(x)

b=[]
for i in range(1,50):
  b.append(2**i)

ct=0
for i in range(len(l2)-1,-1,-1):
    x=math.floor(math.log2(l2[i]))
    x=b[x]-l2[i]
    y=bisect.bisect_left(l2,x)
    if l2[y]==x:
      if l2[y]!=l2[i]:
        m=min(l[i][1],l[y][1])
      else:
        m=l[i][1]//2
      l[i][1]-=m
      l[y][1]-=m
      ct+=m
print(ct)

Solution (Python):
import math
import bisect
n=int(input())
a=list(map(int,input().split()))
a.sort()
b=[]
for i in range(1,50):
  b.append(2**i)
ct=0
check=[1]*n
for i in range(n-1,-1,-1):
  if a[i]==1:
    break
  if check[i]==1 and a[i] not in b:
    check[i]=0
    x=math.floor(math.log2(a[i]))
    x=b[x]-a[i]
    y=bisect.bisect_left(a,x)
    z=bisect.bisect_right(a,x)
    t=bisect.bisect_left(check[y:z],1)+y
    if t!=z:
      check[t]=0
      ct+=1

ctb=0
w=1
for i in range(n):
  if a[i] in b or a[i]==1:
    if a[i]==w:
      if check[i]==1:
        ctb+=1
    else:
      ct+=ctb//2
      w=a[i]
      if check[i]==1:
        ctb=1
      else:
        ctb=0
  else:
    ct+=ctb//2
    ctb=0
ct+=ctb//2

print(ct)

Solution (Python):
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
d={}
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
p=max(a)*2
chk=[pow(2,i) for i in range(1,32)]
ans=0
for i in a[::-1]:
    if d[i]>0:
        d[i]-=1
        for j in chk[::-1]:
            if j-i in d and d[j-i]>0:
                d[j-i]-=1
                ans+=1
                break
print(ans)

Solution (Python):
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
d={}
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
p=max(a)*2
chk=[pow(2,i) for i in range(1,32) if pow(2,i)<=p]
ans=0
for i in a[::-1]:
    if d[i]>0:
        d[i]-=1
        for j in chk[::-1]:
            if j-i in d and d[j-i]>0:
                d[j-i]-=1
                ans+=1
                break
print(ans)

Solution (Python):
n = int(input().strip())
data = list(reversed(sorted(map(int, input().split()))))

cnt = {x: 0 for x in data}
for x in data:
    cnt[x] += 1

ans = 0
t = 2 ** 30
for x in data:
    while t // 2 > x:
        t = t // 2
    while cnt[x] > 0:
        cnt[x] -= 1
        if t-x in cnt and cnt[t-x] > 0:
            cnt[t-x] -= 1
            ans += 1

print (ans)

Solution (Python):
n = int(input())
A = list(map(int,input().split()))
A.append(-float("inf"))
n = len(A)

A.sort()
s = 2
while s <= A[-1]+A[-2]:
    s *= 2
s //= 2

U = [0] * n

ans = 0
while s > 0:
    ll = 0
    rr = n-1
    while rr >= 1 and s <= A[rr]:
        rr -= 1
    while rr >= 1 and rr-ll >= 2:
        
        t = s - A[rr]

        
        l = ll
        r = rr-1
        m = (r+l)//2
        while r-l > 1:
            
            if A[m] >= t:
                r = m
            else:
                l = m
            m = (r+l)//2
        if A[l+1] == t:
            ans += 1
            U[l+1] = 1
            U[rr] = 1
            
            A[l+1] = -float("inf")
        ll = l
        rr -= 1
        
    s //= 2

    B = []
    for i in range(len(A)):
        if U[i] == 0:
            B.append(A[i])
    A = B
    n = len(A)
    U = [0] * n
print(ans)

Solution (Python):

import bisect

"""
def wantp(n):

    wq = []
    while p[n] != n:
        wq.append(n)
        n = p[n]

    for i in wq:
        p[i] = n

    return n
"""


N = int(input())

B = list(map(int,input().split()))
B.sort()

A = []
AS = []
for i in range(N):
    if len(A) == 0:
        A.append(B[0])
        AS.append(1)
    else:
        if A[-1] == B[i]:
            AS[-1] += 1
        else:
            A.append(B[i])
            AS.append(1)


"""
p = [i for i in range(N)]
rank = [1] * N
"""
ans = 0

for i in range(len(A)):

    i = len(A) - 1 - i
    now = 2 ** 33

    while A[i] * 2 < now:
        now //= 2

    ind = bisect.bisect_left(A,now-A[i])

    if A[ind] + A[i] == now:

        if ind == i:
            ans += AS[i] // 2
            AS[i] = AS[i] % 2

        else:
            ans += min(AS[i],AS[ind])
            AS[ind] = max(AS[ind] - AS[i] , 0)



    

print (ans)

Solution (Python):



from collections import Counter
n = int(input())
a = list(map(int, input().split( )))
a_c = Counter(a)

a.sort(reverse = True)
ans = 0
for i in range(n):
    if not a_c[a[i]]:
        continue
    a_c[a[i]] -= 1
    t = (1<<a[i].bit_length()) - a[i]
    if t in a_c:
        if a_c[t]:
            a_c[t] -= 1
            
            ans += 1

print(ans)

Solution (Python):


from collections import Counter
n = int(input())
a = list(map(int, input().split( )))
a_c = Counter(a)

a.sort(reverse = True)
ans = 0
for i in range(n):
    if not a_c[a[i]]:
        continue
    a_c[a[i]] -= 1
    t = (1<<a[i].bit_length()) - a[i]
    if t in a_c:
        if a_c[t]:
            a_c[t] -= 1
            
            ans += 1

print(ans)

Solution (Python):

import sys
input = sys.stdin.buffer.readline

from collections import defaultdict

def getlist():
	return list(map(int, input().split()))



def main():
	
	N = int(input())
	A = getlist()
	D = defaultdict(int)
	for i in A:
		D[i] += 1
	L = []
	for i in D:
		L.append(i)
	L = sorted(L)
	
	
	
	ans = 0
	for i in range(len(L)):
		a = L[-1 - i]
		if a == 2 ** (a.bit_length() - 1):
			ans += int(D[a] // 2)
		else:
			b = 2 ** a.bit_length() - a
			m = min(D[a], D[b])
			ans += m
			D[a] -= m
			D[b] -= m

	
	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
from collections import Counter

n = int(input())
xs = [int(w) for w in input().split()]

counter = Counter(xs)

descent = sorted(xs, reverse=True)

def minimal_greater_power(x):
    b = len("{0:b}".format(x))
    return 2 ** b

ans = 0

for x in descent:
    if x not in counter:
        continue
    if counter[x] == 0:
        continue

    counter[x] -= 1

    pair = minimal_greater_power(x) - x
    if pair not in counter:
        continue
    if counter[pair] == 0:
        continue

    ans += 1
    counter[pair] -= 1

print(ans)

Solution (Python):
import collections
import bisect
n= int(input())
a=list(map(int, input().split()))
c=collections.Counter(a)
ans=0
des=sorted(a,reverse=True)


for i in des:
    if c[i]>0:
        bi=format(i, 'b')
        x=2**len(bi)-i
        c[i]-=1
        if c[x]>0:
            c[x]-=1
            ans+=1
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
d = dict()
ans = 0
for x in a:
  if x not in d:
    d[x] = 0
  d[x] += 1
for x in a:
  t = (1<<x.bit_length()) - x
  f = (d.get(t,0) and d.get(x,0))
  if t == x:
    f = (d.get(t,0) >= 2)
  if f:
    d[x] -= 1
    d[t] -= 1
    ans += 1
print(ans)

Solution (Python):
n = int(input())
A = list(map(int,input().split()))
A.sort(reverse = True)
d = {}
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

ans =0
for a in A:
    b = 2**(a.bit_length())-a
    if b in d:
        if d[b] >=1 and d[a] >= 1:
          if a == b and d[b] ==1:
            continue
          ans += 1 
          d[b]-= 1
          d[a]-= 1

print(ans)

Solution (Python):
N=int(input())
a=list(map(int,input().split()))
a_=sorted(a,key=lambda x:-x)
ans=0
from collections import Counter
c=Counter(a_)
for i in a_:
    if c[i]==0:
        continue
    c[i]-=1
    for n in range(i):
        if i<2**n:
            t=n
            break
        elif i==2**n:
            t=n+1
            break
    j=2**t-i
    if j in c and c[j]>0:
        ans+=1
        c[j]-=1
print(ans)

Solution (Python):
N=int(input())
a=list(map(int,input().split()))
a_=sorted(a,key=lambda x:-x)
ans=0
from collections import Counter
c=Counter(a_)
for i in a_:
    if c[i]==0:
        continue
    c[i]-=1
    m=1<<i.bit_length()
    j=m-i
    if j in c and c[j]>0:
        ans+=1
        c[j]-=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 i in a:
    if c[i] == 0:
        continue
    c[i] -= 1
    k = 1<<i.bit_length()
    j = k-i
    if j in c and c[j] > 0:
        ans += 1
        c[j] -= 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 i in a:
    if c[i] == 0:
        continue
    c[i] -= 1
    k = 1<<i.bit_length()
    j = k-i
    if j in c and c[j] > 0:
        ans += 1
        c[j] -= 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 i in a:
    if c[i] == 0:
        continue
    c[i] -= 1
    k = 1<<i.bit_length()
    j = k-i
    if j in c and c[j] > 0:
        ans += 1
        c[j] -= 1
print(ans)

Solution (Python):
def inv(x):
    z=1
    while z<=x:
        z<<=1
    return z-x

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

d={}
for x in A:
    if x in d:
        d[x]+=1
    else:
        d[x]=1

l=sorted(d,reverse=True)

ans=0

for x in l:
    if d[x]>0:
        y=inv(x)
        if x==y:            
            ans+=d[x]//2
            d[x]%=2
        elif y in d and d[y]>0:
            ans+=min(d[x],d[y])
            d[x],d[y]=d[x]-min(d[x],d[y]),d[y]-min(d[x],d[y])
            
print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
from collections import Counter
c=Counter(A)
r=0
from math import log2
for n in sorted(list(c),reverse=True):
    m=2**int(log2(n)+1)
    if m==2*n:
        r+=c[n]//2
    else:
        r+=min(c[n],c[m-n])
        c[m-n]=max(c[m-n]-c[n],0)
print(r)

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

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

A.sort()
C = Counter(A)

ans = 0
for i in reversed(range(N)):
    a = A[i]
    inv = 2**(a.bit_length())-a
    if a == inv:
        if C[a] >= 2:
            C[a] -= 2
            ans += 1
    elif inv in C.keys():
        if C[inv] >= 1 and C[a] >= 1:
            C[a] -= 1
            C[inv] -= 1
            ans += 1

print(ans)