Problem: 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.

Submission attempts (in order):
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+1,"b")))) - a
    if dic.get(a,0)>0:
        dic[a] -= 1
    if dic.get(small,0)>0:
        dic[small] -= 1
        ans += 1
print(ans)


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
print(dic)
ans = 0

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


import bisect

N = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 0
L=0
t=31
while(t>0):
    if len(A) == 0:
        break
    if A[-1]<(1<<(t-1)) or (1<<t) <= A[-1]:
        t -= 1
        L = 0
        continue

    large = A.pop(-1)
    small = (1<<t)-large
    if small < A[0] or A[-1]< small:
        t -= 1
        L = 0
        continue
    tmp = bisect.bisect_left(A,(1<<t)-large,lo=L,hi=len(A))
    if tmp == len(A):
        t -= 1
        L = 0
        continue
    if A[tmp] == (1<<t)-large:
        del A[tmp]
        ans += 1
        L = max(0,tmp-1)

print(ans)


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 dic.get(a,0)>0 and dic.get(small,0)>0:
        dic[a] = dic.get(a)-1
        dic[small] = dic.get(small)-1
        ans += 1
print(ans)

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
print(dic)
ans = 0

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


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+1,"b")))) - a
    if dic.get(a,0)>0 and dic.get(small,0)>0:
        dic[a] -= 1
        dic[small] -= 1
        ans += 1
print(ans)

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 dic.get(a,0)>0 and dic.get(small,0)>0:
        dic[a] -= 1
        dic[small] -= 1
        ans += 1
print(ans)


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)


Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted