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):
def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    return mid


n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for i in range(n-1):
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        if a[i]==x and a[i+1]==x:
            ans+=1
            a[i]=None
            c=binary_search(a,x)
            a[c]=None
print(ans)

n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for i in range(n):
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        if a[i]==x and a[i+1]==x:
            ans+=1
            a[i]=None
            a[a.index(x)]=None
print(ans)

import copy
import bisect

def index(a, x):
    i = bisect.bisect_right(a, x)

    if i != len(a) and a[i] == x:
        return i
    return -1
    
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
ano_a=copy.copy(a)
ano_a.sort()
for i in range(n-1):
    
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        c=index(ano_a,x)
        if x==a[i] and a[i+1]==x:
            ans+=1
            a[i]=None
            a[c]=None
        elif c>=0:
            if x!=a[i]:
                ans+=1
                a[c]=None
                a[i]=None
print(ans)

import copy
import bisect

def index(a, x):
    i = bisect.bisect_right(a, x)
    a.reverse()
    if i != len(a) and a[i] == x:
        return i
    return -1
    
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
ano_a=copy.copy(a)
ano_a.sort()
for i in range(n):
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        c=index(ano_a,x)
        if x==a[i] and a[i+1]==x:
            ans+=1
            a[i]=None
            a[c]=None
        elif c>=0:
            if x!=a[i]:
                ans+=1
                a[c]=None
                a[i]=None
print(ans)

n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for b in a:
    if b:
        bi=format(b, 'b')
        x=2**len(bi)-b
        if x==b and a.count(x)>1:
            ans+=1
            b=None
            a[a.index(x)]=None
print(ans)



n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for b in a:
    if b:
        bi=format(b, 'b')
        x=2**len(bi)-b
        if x==b:
            ans+=1
            b=None

print(ans)



n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for b in a:
    if b:
        bi=format(b, 'b')
        x=2**len(bi)-b
        if x==b and a.count(x)>1:
            ans+=1
            b=None
            a[a.index(x)]=None
        else:
            ans+=1
            a[a.index(x)]=None
            b=None
print(ans)
  

import copy
import bisect

def index(a, x):
    i = bisect.bisect_right(a, x)
    a.reverse()
    if i != len(a) and a[i] == x:
        return i
    return -1
    
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
ano_a=copy.copy(a)
ano_a.sort()
for i in range(n):
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        c=index(ano_a,x)
        if x==a[i] and a[i+1]==x:
            ans+=1
            a[i]=None
            a[c]=None
        elif c>=0:
            if x!=a[i]:
                ans+=1
                a[c]=None
                a[i]=None
print(ans)

n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for b in a:
    if b:
        bi=format(b, 'b')
        x=2**len(bi)-b
        if x==b and a.count(x)>1:
            ans+=1
            b=None

print(ans)



n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
for i in range(n):
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        if a[i]==x and a[i+1]==x:
            ans+=1
            a[i]=None
print(ans)

import copy
import bisect

def index(a, x):
    i = bisect.bisect_right(a, x)
    a.reverse()
    if i != len(a) and a[i] == x:
        return i
    return -1
    
n= int(input())
a=list(map(int, input().split()))
ans=0
a.sort(reverse=True)
ano_a=copy.copy(a)
ano_a.sort()
for i in range(n-1):
    
    if a[i]:
        bi=format(a[i], 'b')
        x=2**len(bi)-a[i]
        c=index(ano_a,x)
        if x==a[i] and a[i+1]==x:
            ans+=1
            a[i]=None
            a[c]=None
        elif c>=0:
            if x!=a[i]:
                ans+=1
                a[c]=None
                a[i]=None
print(ans)

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)

Verdicts: Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Accepted