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
def debug(*args): print(*args, file=sys.stderr)
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:
    
    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
    if C[larger_nibeki(a) - a] > 0:
        ans += 1
        C[larger_nibeki(a) - a] -= 1
print(ans)

Solution (Python):
import math
from collections import Counter


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

n_pears = 0
counter = Counter(A)

for i in reversed(range(0, len(A))):
    if counter[A[i]] <= 0:
        continue
    counter[A[i]] -= 1
    Aj = 2 ** int(math.log2(A[i]) + 1) - A[i]
    if counter[Aj] > 0:
        n_pears += 1
        counter[Aj] -= 1

print(n_pears)

Solution (Python):

import sys, os
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
def debug(*args): pass 
def exit(): sys.exit(0)


n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = a[-1]
m = 0
while True:
    if 2**m > max_a:
        break
    m += 1
used = [False] * n


def bisect(val, start, end):
    debug(used)
    if start >= end:
        return None
    elif start + 1 == end:
        if a[start] == val:
            if used[start]:
                return None
            used[start] = True
            return start
        else:
            return None
    mid = (start + end) // 2
    if a[mid] == val:
        if used[mid]:
            res = bisect(val, start, mid)
            return res
        else:
            res = bisect(val, mid+1, end)
            if res is not None:
                return res
            used[mid] = True
            return mid
        
        
        
        
        
        
        
        
        
        
    elif a[mid] > val:
        return bisect(val, start, mid)
    else:
        return bisect(val, mid, end)
    
    
    
    
    return None


def _find(b, end, e):
    
    val = 2**e - b
    if val <= 0:
        return None
    return bisect(val, 0, end)
    
    
    
    
    


def find(b, end):
    for e in reversed(range(m+1)):
        res = _find(b, end, e)
        if res is not None:
            return True
    return False


ans = 0
for j in reversed(range(n)):
    if used[j]:
        continue
    b = a[j]
    used[j] = True
    res = find(b, j)
    if res:
        ans += 1


print(ans)

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

xs = sorted(A, reverse=True)

cs = {}

for x in xs:
    cs[x] = cs.get(x, 0) + 1

result = 0

for x in xs:
    if cs[x]:
        for i in range(31, 0, - 1):
            m = 2**i
            y = m - x
            if y > x or y < 1:
                continue
            if y in cs:
                if x == y:
                    if cs[y] >= 2:
                        cs[y] -= 2
                        result += 1
                        break
                else:
                    if cs[y] >= 1:
                        cs[x] -= 1
                        cs[y] -= 1
                        result += 1
                        break


print(result)

Solution (Python):
from bisect import bisect
N = int(input())
*A, = map(int, input().split())
B = {}
for a in A:
    B[a] = B.get(a, 0) + 1
R = sorted(B.items())
C = []; D = []
for k, v in sorted(B.items()):
    C.append(k)
    D.append(v)
M = len(C)
j = 0
ans = 0
for i in range(M-1, -1, -1):
    if D[i] == 0:
        continue
    a = C[i]
    b = 2**a.bit_length()
    j = bisect(C, b-a-1)
    if j < M and C[j] == b-a:
        if i == j:
            c = D[i]//2
        else:
            c = min(D[i], D[j])
        ans += c
        D[i] -= c; D[j] -= c
print(ans)

Solution (Python):
input()
a=sorted(map(int,input().split()))[::-1]
s={}
l=[2**-~i for i in range(31)[::-1]]
r=0
for v in a:
	for j in l:
		p=j-v
		if p in s and s[p]>0:r+=1;s[p]-=1;break
	else:s[v]=s.get(v,0)+1
print(r)

Solution (Python):
import sys
import socket
from collections import Counter

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('b1.in')


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


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


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    res = 0
    n = read_int()
    a = read_int_list()
    a.sort()
    c = Counter(a)
    for i in range(n - 1, -1, -1):
        if c[a[i]] <= 0:
            continue
        c[a[i]] -= 1
        p = 1
        while not p <= a[i] < 2 * p:
            p *= 2
        comp = 2 * p - a[i]
        if c[comp] > 0:
            c[comp] -= 1
            res += 1
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

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


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


count_e = defaultdict(lambda: 0)
count_o = defaultdict(lambda: 0)
for a in aaa:
    if a % 2 == 0:
        count_e[a] += 1
    else:
        count_o[a] += 1

print(solve(count_e) + solve(count_o))

Solution (Python):
import math,collections
n=int(input())
a=sorted(map(int,input().split()))[::-1]
s=collections.Counter(a)
r=0
f=0
for i,v in enumerate(a):
	p=2**math.ceil(math.log2(v))-v
	if f:f=0
	elif s[v]==0:pass
	elif p in s.keys()and s[p]>0:s[v]-=1;s[p]-=1;r+=1
	elif i<n-1 and p==0 and v==a[i+1]and s[v]>1:s[v]-=2;r+=1;f=1
print(r)

Solution (Python):

from bisect import bisect, bisect_left
from collections import defaultdict

def inpl(): return list(map(int, input().split()))
N = int(input())
A = sorted(inpl())
beki = [2**i for i in range(1, 31)]
D = defaultdict(list)


for i, a in enumerate(A):
    D[a].append(i)

answer = 0
matched = [0]*(N)

for t in range(31, 0, -1):
    S = 2 ** (t)
    R = bisect_left(A, S) - 1
    for i in range(R, 0, -1):
        if A[i] + A[i-1] < S:
            break
        if matched[i]:
            continue
        X = S - A[i]
        if len(D[X]) >= 1 + (X == A[i]):
            a = D[A[i]].pop()
            b = D[X].pop()
            assert a == i
            matched[a] = 1
            matched[b] = 1
            answer += 1
print(answer)

Solution (Python):
import math,collections
n=int(input())
a=sorted(map(int,input().split()))[::-1]
s=collections.Counter(a)
r=0
f=0
for i,v in enumerate(a):
	if f:f=0;continue
	if s[v]==0:continue
	p=2**math.ceil(math.log2(v))-v
	if p in s.keys() and s[p]>0:s[v]-=1;s[p]-=1;r+=1;continue
	if i<n-1 and p==0 and a[i+1]==v and s[v]>=2:s[v]-=2;r+=1;f=1
print(r)

Solution (Python):
import bisect
import math
N = int(input())
A = list(map(int, input().split()))
A.sort()
already = set()
key = {}

def is_in(t, n):
    i = key.setdefault(t, bisect.bisect_left(A, t))
    if i >= n:
        return -1

    while i < n and t == A[i]:
        if i not in already:
            already.add(i)
            key[t] = i
            return i
        i += 1

    return -1

res = 0
for n in range(len(A) - 1, -1, -1):
    if n in already:
        continue

    a = A[n]
    t = 1 << (int(math.log2(a)) + 1)

    while t > a:
        i = is_in(t - a, n)
        if i != -1:
            res += 1
            break
        t >>= 1

print(res)
print("")

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
import math
N = int(input())
A = list(map(int, input().split()))
T = [2 ** i for i in range(31)]
A.sort()
already = set()


def to_dic(A):
    d = {}
    for a in A:
        d[a] = d.setdefault(a, 0) + 1

    return d

def is_in(t, num):
    i = D.setdefault(t, 0)
    if i == 0:
        return 0
    s = min(i, num)
    D[t] -= s
    return s


res = 0
D = to_dic(A)
A2 = list(D.keys())
A2.sort()

for n in range(len(A2) - 1, -1, -1):
    a = A2[n]

    if a in T:
        res += D[a] // 2
        D[a] = 0

        if D[a] % 2 == 0:
            continue

    num = D[a]
    t = 1 << (int(math.log2(a)) + 1)

    while t > a:
        s = is_in(t - a, num)
        res += s
        num -= s
        if num == 0:
            break

        t >>= 1

print(res)

Solution (Python):
N=int(input())
A=sorted([int(i) for i in input().split()],reverse=True)
B=[2**(len(bin(i))-2) for i in A]
D=dict()
for i in range(N):
    if not(A[i] in D):
        D[A[i]]=1
    else:
        D[A[i]]+=1
ans=0
for i in range(N):
    if D[A[i]]<=0:
        continue
    if B[i]==2*A[i]:
        if D[A[i]]>=2:
            D[A[i]]-=2
            ans+=1
    else:
        if (B[i]-A[i]) in D:
            if D[B[i]-A[i]]!=0:
                D[A[i]]-=1
                D[B[i]-A[i]]-=1
                ans+=1
print(ans)

Solution (Python):
import bisect
ans = 0
N = int(input())
a = list(map(int,input().split()))
b = [True for _ in range(N)]
c = [True for _ in range(N)]
a.sort()
digit = 40
y = 2 ** (digit+1) -1
while len(a)>1:
    if b[-1]==False:
        a.pop(-1)
        b.pop(-1)
        continue
    x = a.pop(-1)
    b.pop(-1)
    while x < 2**digit:
        digit -= 1
        y = 2 ** (digit+1) -1
    z = x^y
    z += 1
    ll =  bisect.bisect_left(a,z)
    rr =  bisect.bisect_right(a,z)
    if rr-ll>0:
        rr -= 1
        if b[ll]==False:
            pass
        elif b[rr]==True:
            b[rr]=False
            ans += 1
        else:
            lll = ll
            rrr = rr
            while rrr-lll>1:
                if b[(rrr+lll)//2]:
                    lll = (rrr+lll)//2
                else:
                    rrr = (rrr+lll)//2
            b[lll] = False
            ans += 1           
print(ans)

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):




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

    dic = {}
    for i in a:
        dic[i] = dic.get(i, 0) + 1

    a.sort(reverse=True)

    ans = 0
    for i in a:
        if i not in dic:
            continue
        dic[i] -= 1
        if not dic[i]:
            del dic[i]

        j, cnt = i, 1
        while j:
            j >>= 1
            cnt *= 2

        num = cnt - i
        if num in dic:
            dic[num] -= 1
            ans += 1
            if not dic[num]:
                del dic[num]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):





"""
agc 029 B
"""

from collections import Counter

nn = int(input())
ali = list(map(int, input().split()))
ali.sort(reverse=True)

c = Counter(ali)
ans = 0


def pow2(n):
    m = n
    tmp = 1
    while m > 0:
        tmp = tmp << 1
        m = m >> 1
    return tmp


ii = 0
m = ali[ii]
while bool(c):
    while c[ali[ii]] == 0:
        ii += 1
    m = ali[ii]
    n = pow2(m) - m
    c[m] -= 1
    if c[m] <= 0:
        del c[m]
    if n in c:
        c[n] -= 1
        if c[n] <= 0:
            del c[n]
        ans += 1

print(ans)

Solution (Python):
from collections import Counter
import math

N=int(input())

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

answer=0
A.sort(reverse=True)

Amax=A[0]
limit=1
while(True):
  if limit>Amax:
    break;
  limit*=2

Acounter=Counter(A)


while(limit!=1):
  eraserlist=[]
  for number,count in Acounter.items():
    if limit-number in Acounter.keys():
      if number==limit-number:
        dec=math.floor(Acounter[number]/2)
        Acounter[number]-=dec*2
      else:
        dec=min(Acounter[number],Acounter[limit-number])
        Acounter[number]-=dec
        Acounter[limit-number]-=dec
        if Acounter[limit-number]==0:
          eraserlist.append(limit-number)
      if Acounter[number]==0:
        eraserlist.append(number)
      answer+=dec
    if number>=limit/2:
      eraserlist.append(number)
  for i in range(len(eraserlist)):
    if eraserlist[i] in Acounter.keys():
      Acounter.pop(eraserlist[i])
  limit=int(limit/2)
print(answer)

Solution (Python):

from bisect import bisect, bisect_left
from collections import defaultdict

def inpl(): return list(map(int, input().split()))
N = int(input())
A = sorted(inpl())
beki = [2**i for i in range(1, 31)]
D = defaultdict(list)


for i, a in enumerate(A):
    D[a].append(i)

answer = 0
matched = [0]*(N)

for t in range(31, 0, -1):
    S = 2 ** (t)
    R = bisect_left(A, S) - 1
    for i in range(R, 0, -1):
        if A[i] + A[i-1] < S:
            break
        if matched[i]:
            continue
        X = S - A[i]
        if len(D[X]) >= 1 + (X == A[i]):
            a = D[A[i]].pop()
            b = D[X].pop()
            assert a == i
            matched[a] = 1
            matched[b] = 1
            answer += 1
print(answer)

Solution (Python):

import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = a[-1]
m = 0
while True:
    if 2**m > max_a:
        break
    m += 1
used = [False] * n


def bisect(val, start, end):
    if start >= end:
        return None
    elif start + 1 == end:
        if a[start] == val:
            if used[start]:
                return None
            used[start] = True
            return start
        else:
            return None
    mid = (start + end) // 2
    if a[mid] == val:
        if used[mid]:
            res = bisect(val, start, mid)
            return res
        else:
            res = bisect(val, mid+1, end)
            if res is not None:
                return res
            used[mid] = True
            return mid
        
        
        
        
        
        
        
        
        
        
    elif a[mid] > val:
        return bisect(val, start, mid)
    else:
        return bisect(val, mid, end)
    
    
    
    
    return None


def _find(b, end, e):
    "slow!!!!"
    
    val = 2**e - b
    if val <= 0:
        return None
    return bisect(val, 0, end)
    
    
    
    
    


def find(b, end):
    for e in reversed(range(m+1)):
        res = _find(b, end, e)
        if res is not None:
            return True
    return False


ans = 0
for j in reversed(range(n)):
    if used[j]:
        continue
    b = a[j]
    used[j] = True
    res = find(b, j)
    if res:
        ans += 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 math import log
from bisect import bisect_left


def log2(x):
    return log(x, 2)


def getComp(n):
    return (1 << (1 + int(log2(n)))) - n


N = int(input())
A = [int(s) for s in input().split()]
A.sort()
B = []
C = []
i = 0
while i < len(A):
    j = i
    count = 1
    while i+1 < len(A) and A[j] == A[i+1]:
        count += 1
        i += 1
    B.append(A[j])
    C.append(count)
    i += 1

count = 0
i = len(B) - 1
while i >= 0:
    comp = getComp(B[i])
    j = bisect_left(B, comp)
    if i == j and C[i] < 2:
        i -= 1
        continue
    if B[j] != comp:
        i -= 1
        continue
    if not C[i] or not C[j]:
        i -= 1
        continue
    C[i] -= 1
    C[j] -= 1
    count += 1

print(count)

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

from collections import Counter
counter=Counter(A)

LIST=sorted(list(counter.keys()),reverse=True)

L=len(LIST)

i=0
ANS=0
while i<L:
    
    if counter[LIST[i]]==0:
        i+=1
    else:
        for k in range(1,33):
            if 2**k<=LIST[i]:
                continue
            if 2**k>LIST[i]*2:
                i+=1
                break
            if counter.get(2**k-LIST[i],0)>0:
                if LIST[i]!=2**k-LIST[i]:
                    x=min(counter[LIST[i]],counter[2**k-LIST[i]])
                    counter[LIST[i]]-=x
                    counter[2**k-LIST[i]]-=x
                    ANS+=x
                else:
                    if counter[LIST[i]]>=2:
                        x=counter[LIST[i]]//2
                        counter[LIST[i]]-=x*2
                        ANS+=x
                    

print(ANS)

Solution (Python):



import bisect
import collections

n=int(input())
a = [int(i) for i in input().split()]
a.sort()


checked=collections.Counter(a)

ans=0

while(a):
    c=a.pop()
    if checked[c]==0:
        continue
    checked[c]-=1
    d=c
    keta=0
    while(d!=0):
        d=d//2
        keta +=1
    x = 2**keta - c

    i = bisect.bisect_right(a, x)
    if i and a[i-1] == x and checked[x]>0:
        ans += 1
        checked[x]-=1
        







print(ans)

Solution (Python):
from collections import defaultdict
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:
    
    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):
import math
import collections
n=int(input())
a=sorted(map(int,input().split()))[::-1]
s=collections.Counter(a)
r=0
flag=False
for i in range(n):
    
    if flag:
        flag=False
        continue
    if s[a[i]]==0: continue
    pair = 2**math.ceil(math.log2(a[i]))-a[i]
    
    if pair in s.keys() and s[pair]>0:
        s[a[i]]-=1
        s[pair]-=1
        r+=1
        continue
    if i<n-1 and pair==0 and a[i+1]==a[i] and s[a[i]]>=2:
        s[a[i]]-=2
        r+=1
        flag=True
print(r)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A = sorted(A, reverse = True)
d = {} 
ans = 0
for i in A:
	for j in range(31, 0, -1):
		x = 2 ** j - i
		if x in d and d[x] > 0:
			ans = ans + 1
			d[x] -= 1
			break
	else:
		d[i] = d.get(i, 0) + 1
print(ans)

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(58):
    Ps.append(Ps[-1] * 2)
Ps = Ps[::-1]

ans = 0
for A in As:
    if cnt[A] <= 0: continue
    cnt[A] -= 1
    for P in Ps:
        if cnt[P - A] > 0:
            ans += 1
            cnt[P - A] -= 1
            break
print(ans)

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

ans1, ans2 = 0,0

maxA = max(A)
B = [1]
t = 1
while t < maxA:
    t *= 2
    B.append(t)

d = dict()
for i in range(N):
    if A[i] in d:
        d[A[i]] += 1
    else:
         d[A[i]] = 1

for i in range(N):
    t = 2**len(bin(A[i])[2::]) - A[i]
    if t in d:
        if t != A[i]:
            if d[t]>0 and d[A[i]]>0:
                ans2 += 1
                d[t] -= 1
                d[A[i]] -= 1
        else:
            if d[t] > 1:
                ans2 += 1
                d[t] -= 2


print(ans1+ans2)

Solution (Python):
from bisect import bisect_right as br
from collections import Counter
n = int(input())
cnt = Counter(list(map(int, input().split())))
keys = sorted(cnt.keys(), reverse=True)
bs = [2 ** i for i in range(32)]
ans = 0
for k in keys:
  if k in bs:
    while cnt[k] >= 2:
      cnt[k] -= 2
      ans += 1
    continue
  to = bs[br(bs, k)] - k
  while cnt[k] > 0:
    if to in cnt and cnt[to]:
      ans += 1
      cnt[to] -= 1
      cnt[k] -= 1
    else:
      break
print(ans)

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    retval = 0
    memo = {}
    for a in A:
        pair_created = False
        for i in range(30, 0, -1):
            s = pow(2, i)
            if a < s and (s-a) in memo and memo[s-a]:
                memo[s-a] -= 1
                pair_created = True
                break
        if pair_created:
            retval += 1
            continue
        if a not in memo:
            memo[a] = 0
        memo[a] += 1
    print(retval)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
a.sort(key=lambda x:-x)
d = defaultdict(int)
for i in a:
    d[i] += 1
beki = [2**i for i in range(32,0,-1)]
ans = 0
for i in a:
    if d[i] == 0:
        continue
    for j in beki:
        if j <= i:
            break
        ni = j - i
        if ni == i:
            if d[i] >= 2:
                ans +=1
                d[i]-=2
                break
        elif d[ni] > 0:
            ans += 1
            d[ni]-=1
            d[i]-=1
            break
print(ans)

Solution (Python):
from collections import Counter
N, = map(int, raw_input().split())
A = map(int, raw_input().split())
c = Counter(A)
ks = c.keys()
ks.sort()
r = 0
for i in ks[::-1]:
  for j in xrange(60):
    p = 1<<j
    if i<=p:
      break
  if p==i:
    r += c[i]//2
  else:
    q = p-i
    x = min(c[i], c[q])
    r += x
    c[i] -= x
    c[q] -= x
print r

Solution (Python):
import bisect

import collections


n = int(input())
a = list(map(int, input().split()))
a_counter = collections.Counter(a)
a_keys = sorted(a_counter.keys(), reverse=True)

targets = []

t = 0
vt = 1
for v in a:
    while v >= vt:
        t += 1
        vt *= 2
        targets.append(vt)
targets.reverse()


cnt = 0
for key in a_keys:
    if a_counter[key] <= 0:
        continue
    for t in targets:
        if key >= t:
            break
        if key == t-key:
            p = max(0, min(a_counter[key], a_counter[t-key])) // 2
        else:
            p = max(0, min(a_counter[key], a_counter[t-key]))
        a_counter[key] -= p
        a_counter[t-key] -= p
        cnt += p
print(cnt)

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):

import math

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

A_dict = dict()
for a in A_list:
    if a in A_dict.keys():
        A_dict[a] += 1
    else:
        A_dict[a] = 1

res = 0
A_list_ = list(reversed(sorted(A_list)))
for a in A_list_:
    
    r = 2**math.ceil(math.log2(a))
    if a == r:
        res += A_dict[a] // 2
        A_dict[a] = 0
    else:
        b = r - a
        if A_dict[a] > 0 and A_dict.get(b, 0) > 0:
            A_dict[a] -= 1
            A_dict[b] -= 1
            res += 1
print(res)

Solution (Python):
from bisect import bisect
N = int(input())
*A, = map(int, input().split())
B = {}
for a in A:
    B[a] = B.get(a, 0) + 1
R = sorted(B.items())
C = []; D = []
for k, v in sorted(B.items()):
    C.append(k)
    D.append(v)
M = len(C)
j = 0
ans = 0
for i in range(M-1, -1, -1):
    if D[i] == 0:
        continue
    a = C[i]
    b = 2**(a).bit_length()
    j = bisect(C, b-a-1)
    if j < M and C[j] == b-a:
        if i == j:
            ans += D[i]//2
            D[i] %= 2
        else:
            c = min(D[i], D[j])
            ans += c
            D[i] -= c; D[j] -= c
print(ans)

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 collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    
    import numpy
    def dprint(*args, **kwargs):
        
        
        print(*args,  file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') 
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') 
    atexit.register(lambda :sys.stdout.close())     
zp = []
for i in range(1, 31):
    zp.append(2**i)

dprint(zp)
    
N, = getIntList()


za = getIntList()

tc = collections.Counter(za)
za.sort(reverse = True)

r = 0
for x in za:
    if tc[x]==0: continue
    tc[x] -= 1
    for y in zp:
        if y<= x: continue
        g = y - x
        if g> x:
            break
        if tc[g] >0:
            r +=1
            tc[g] -=1
print(r)

Solution (Python):
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
A.sort()
d = defaultdict(int)
for a in A:
    d[a] += 1
ans = 0

for i in range(N-1, -1, -1):
    a = A[i]
    if d[a] == 0:
        continue
    s = 2**(len(bin(a))-2)
    p = s-a
    if (d[p] > 0 and p!=a) or d[p]>1:
        ans += 1
        d[p] -= 1
        d[a] -= 1
print(ans)