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

n = int(input())
a = [int(item) for item in input().split()]
a.sort()
ca = Counter(a)
max_a = a[-1] 

ans = 0
for item in a[::-1]:
    if ca[item] == 0:
        continue
    for i in range(31, 0, -1):
        inv = (1 << i) - item
        if inv < 0 or inv > max_a:
            continue
        if item == inv:
            if ca[inv] > 1:
                ans += 1 
                ca[inv] -= 2
                break
        else:
            if ca[inv] > 0:
                ans += 1 
                ca[inv] -=1
                ca[item] -=1
                break
print(ans)

Solution (Python):


import sys
from collections import defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7
dy, dx = (0, -1, 0, 1), (1, 0, -1, 0)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    A = LI()

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

    key_n = list(MA.keys())
    key_n.sort()
    key_n.reverse()

    res = 0
    p = 30
    for x in key_n:
        
        if not MA[x]:
            continue

        
        
        
        while 2 * x < 2 ** p:
            p -= 1

        if x + 1 <= 2 ** p:
            y = 2 ** p - x
            if not MA[y]:
                continue

            if x == y:
                _add = MA[x] // 2
            else:
                _add = min(MA[x], MA[y])

            res += _add
            MA[x] -= _add
            MA[y] -= _add

    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
F = sys.stdin
N = int(F.readline().strip("\n"))
A = list(map(int, F.readline().strip("\n").split()))
A.sort()

pair_sum = 0
A_dict = dict()
for a in A:
    if a not in A_dict: A_dict[a] = 1
    else: A_dict[a] += 1

for i in reversed(range(1, N)):
    if A_dict[A[i]] > 0:
        nowA = A[i]
        temp_a = A[i]
        k = 0
        while temp_a > 0:
            temp_a //= 2
            k += 1
        opposite = 2 ** k - nowA
        if opposite in A_dict:
            if opposite == nowA and A_dict[opposite] > 1:
                pair_sum += 1
                A_dict[opposite] -= 2
            elif opposite != nowA and A_dict[opposite] > 0:
                pair_sum += 1
                A_dict[opposite] -= 1
                A_dict[nowA] -= 1

print(pair_sum)

Solution (Python):
N  =  int(input())
A  =  list(map(int, input().split()))
A.sort(reverse = True)
d  =  {}
cnt = 0

for a in A:
    if a not in d:
        d[a] = 1
    else:
        d[a] += 1
    
for i in range(N):
    if d[A[i]] == 0:
        continue
        
    d[A[i]] -= 1
    
    temp = 2 ** A[i].bit_length() - A[i]
    
    if temp in d and d[temp] > 0:
        cnt += 1
        d[temp]  -= 1
        
print(cnt)

Solution (Python):
n  =  int(input())
a  =  list(map(int, input().split()))
a.sort(reverse = True)
d  =  {}
count = 0

for x in a:
    if x not in d: d[x] = 0
    d[x] += 1
    
for i in range(len(a)):
    if d[a[i]] == 0:
        continue
        
    d[a[i]] -= 1
    
    y = 2**a[i].bit_length() - a[i]
    
    if y in d and d[y] > 0:
        count += 1
        d[y]  -= 1
        
print(count)

Solution (Python):



import bisect
from collections import defaultdict

N = int(input())
X = sorted(list(map(int, input().rstrip().split(' '))), reverse=False)
included_X = defaultdict(int)
pow_2 = [2**i for i in range(1, 50)]

for x in X:
    included_X[x] += 1

count = 0
for i, x in enumerate(X[::-1]): 
    if included_X[x] > 0:
        index = bisect.bisect_left(pow_2, x + 1)
        if pow_2[index] - x == x:
            if included_X[pow_2[index] - x] > 1:
                included_X[pow_2[index] - x] -= 2
                count += 1
        else:
            if included_X[pow_2[index] - x] > 0:
                included_X[pow_2[index] - x] -= 1
                included_X[x] -= 1
                count += 1
         
print(count)

Solution (Python):
from collections import Counter


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


C = Counter(A)
ans = 0
for m in sorted(C, reverse=True):
    p = (1 << m.bit_length()) - m
    if m == p:
        ans += C[m] // 2
    elif p in C:
        k = min(C[m], C[p])
        ans += k
        C[p] -= k


print(ans)

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
ctr = Counter(A)
sa = sorted(ctr.keys(),reverse=True)

ans = 0
for a in sa:
    p = 2**(len(bin(a))-2)
    rem = p - a
    if a == rem:
        v = ctr[a] // 2
    else:
        v = min(ctr[a], ctr[rem])
    ans += v
    ctr[a] -= v
    ctr[rem] -= v
print(ans)

Solution (Python):
n  =  int(input())
a  =  list(map(int, input().split()))
a.sort(reverse = True)
d  =  {}
count = 0

for x in a:
    if x not in d: d[x] = 0
    d[x] += 1
    
for i in range(len(a)):
    if d[a[i]] == 0:continue
        
    d[a[i]] -= 1
    
    y = 2**a[i].bit_length() - a[i]
    
    if y in d and d[y] > 0:
        count += 1
        d[y]  -= 1
        
print(count)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a.sort()
from collections import Counter
dic = Counter(a)
ans = 0
for k in range(len(a)-1,-1,-1):
    if dic[a[k]]==0:
        continue
    dic[a[k]] -= 1
    t = 2**a[k].bit_length()-a[k]
    if dic[t]:
        dic[t] -= 1
        ans += 1
print(ans)

Solution (Python):
import bisect

def binum(num):
	number_len = len(bin(num))-2
	f = 2**number_len -1
	return (num^f)+1

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

while len(A) > 0:
	k = A.pop()
	if len(A) == 0:
		break
	if int(k) != k:
		continue
	x = binum(k)
	if x > A[-1]:
		continue
	if A[bisect.bisect_left(A,x)] == x:
		A[bisect.bisect_left(A,x)] -= 0.5
		cnt += 1

print(cnt)

Solution (Python):
import bisect

def number(num):
  
  number_len = len(bin(num))-2
  
  f = 2**number_len - 1
  
  return (num^f)+1

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

line.sort()

count=0

while len(line)>0:
  
  k=line.pop()
  
  if len(line)==0:
    break
  
  if int(k) != k:
    continue
  x=number(k)
  
  if x>line[-1]:
    continue
  
  if line[bisect.bisect_left(line,x)]==x:
    
    line[bisect.bisect_left(line,x)] -= 0.5
    count+=1

print(count)

Solution (Python):
import bisect
def reversed_num(num):
  num_len=len(bin(num))-2
  f=2**num_len-1
  return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
  k=number.pop()
  if len(number)==0:
    break
  if k==int(k):
    x=reversed_num(k)+1
    y=bisect.bisect_left(number,x)
    if x>number[-1]:
      y-=1
    if number[y] ==x:
      number[y]-=0.5
      count+=1
print(count)

Solution (Python):
import sys
import collections

def solve():
    N = int(sys.stdin.readline().rstrip())
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    A = sorted(A, reverse=True)
    maxA = A[0]
    cntA = collections.Counter(A)

    ans = 0
    for a in A:
        if cntA[a] == 0:
            continue
        cntA[a] -= 1
        
        b = (1 << a.bit_length()) - a
        if cntA[b] > 0:
            cntA[b] -= 1
            ans += 1
    return ans

print(solve())

Solution (Python):
import bisect
inpl = lambda: list(map(int,input().split()))
_ = int(input())
A = sorted(inpl())
Anlist = []
ap = 0
for a in A:
  if a > ap:
    Anlist.append([a,1])
    ap = a
  else:
    Anlist[-1][1] += 1

A = [ a for a,n in Anlist ]
N = len(Anlist)

ans = 0
for i in range(1,N+1):
  if Anlist[-i][1] == 0:
    continue
  
  p = len(bin(A[-i]))-3
  B = (1 << (p+1)) - A[-i]
  if A[-i] == B:
    ans += Anlist[-i][1]//2
  else:
    m = bisect.bisect_left(A,B,0,N-i)
    if m < N-i and A[m] == B:
      pairs = min(Anlist[m][1],Anlist[-i][1])
      ans += pairs
      Anlist[m][1] -= pairs

print(ans)

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import deque

N = int(input())
A = list(map(int, input().split(" ")))
A.sort()
A = deque(A)
ans = 0
t_max = len(bin(A[-1])) - 2
for t in range(t_max, 0, -1):
    if len(A) < 2: break
    while len(bin(A[-1])) - 2 > t:
        A.pop()
        if len(A) < 2: break
    if len(A) < 2: break
    pow2 = 1 << t
    A_tmp = deque()
    while t == len(bin(A[-1])) - 2:
        r = A.pop()
        idx = bisect_left(A, pow2 - r)
        for _ in range(idx):
            A_tmp.appendleft(A.popleft())
        if len(A) == 0: break
        if A[0] + r == pow2:
            A.popleft()
            ans += 1
        if len(A) < 2: break
    A.extendleft(A_tmp)
                    
print(ans)

Solution (Python):

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    A = []
    input_raw = read_func().strip().split()
    for i in range(N):
        A.append(int(input_raw[i]))

    pair_count = 0
    already_set = set([])
    for t in range(31, 0, -1):
        x = 2**t
        count_dict = {}
        for i in range(N):
            if i in already_set:
                continue
            if x - A[i] <= 0:
                continue
            if x - A[i] in count_dict and len(count_dict[x - A[i]]) > 0:
                pair_count += 1
                j = count_dict[x - A[i]].pop()
                already_set.add(i)
                already_set.add(j)
            else:
                if A[i] not in count_dict:
                    count_dict[A[i]] = [i]
                else:
                    count_dict[A[i]].append(i)

    print pair_count

if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
N = int(input())
A_arr = list(map(int, input().split()))

A_arr = sorted(A_arr, reverse=True)
C_arr = Counter(A_arr)

count = 0
for i in range(N):
    v_max = A_arr[i]
    if C_arr[v_max] == 0:
        continue
    C_arr[v_max] -= 1
    v_pair = 2**v_max.bit_length() - v_max
    if C_arr[v_pair] > 0:
        C_arr[v_pair] -= 1
        count += 1
    else:
        pass

print(count)

Solution (Python):
import collections

N = int(input())
A = collections.deque(sorted(map(int,input().split())))


def func1(a, r, rnext):
    p = a.popleft()
    q = a.pop()
    ans = 0
    a1 = collections.deque()
    while True:
        if p + q == r:
            ans += 1
            try:
                p = a.popleft()
            except:
                break
            try:
                q = a.pop()
            except:
                if p < rnext:
                    a1.append(p)
                break
        elif p + q > r:
            try:
                q = a.pop()
            except:
                if p < rnext:
                    a1.append(p)
                break
        else:
            a1.append(p)
            try:
                p = a.popleft()
            except:
                if q < rnext:
                    a1.append(q)
                break
    return ans, a1


if N == 1:
    print(0)
    exit(0)
t = int.bit_length(A[-1] + A[-2])
r = 2 ** t
rnext = 2 ** (t - 1)
anser = 0
a = A

while True:
    ans, a1 = func1(a, r, rnext)
    anser += ans
    if len(a1) < 2:
        break
    a = a1
    t -= 1
    r = rnext
    rnext = 2 ** (t - 1)

print(anser)

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 x in a:
    if c[x] == 0:
        continue
    temp = (1 << x.bit_length()) - x
    c[x] -= 1
    if temp in c.keys():
        if c[temp] > 0:
            c[temp] -= 1
            ans += 1

print(ans)

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

A.sort(reverse=True)

dic = {}
for i in range(N):
    if A[i] in dic:
        dic[A[i]] += 1
    else:
        dic[A[i]] = 1
 
res = 0
for i in range(N):
    if A[i] in dic:
        n = 0
        tmp = A[i]
        while True:
            if tmp == 0:
                break
            tmp //= 2
            n += 1

        if 2 ** n - A[i] in dic:
            if 2 ** n - A[i] == A[i] and dic[A[i]] < 2:
                pass
            else:
                res += 1
                dic[2 ** n - A[i]] -= 1
                if dic[2 ** n - A[i]] == 0:
                    dic.pop(2 ** n - A[i])

        dic[A[i]] -= 1
        if dic[A[i]] == 0:
            dic.pop(A[i])
        
print(res)

Solution (Python):
def hersCode(L, n):
  ok = len(L) - 1
  ng = 0
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] > n:
      ok = mid
    else:
      ng = mid
  return ok

def hersCode2(L, n):
  ok = 0
  ng = len(L)
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] < n:
      ok = mid
    elif L[mid] == n:
      if TF[mid]:
        ok = mid
      else:
        ng = mid
    else:
      ng = mid
  return ok

N = int(input())

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

D = [pow(2, i) for i in range(31)]
TF = [True for i in range(N + 1)]
Ans = 0
A = [-1e11] + A
for i in range(len(A) - 1, 1, -1):
  if TF[i]:
    k = D[hersCode(D, A[-1])] - A[-1]
    del A[-1]
    t = hersCode2(A, k)
    if A[t] == k:
      TF[t] = False
      Ans += 1
  else:
    del A[-1]

print(Ans)

Solution (Python):
import bisect
N=int(input())
A=list(map(int,input().split()))
A.sort()
A.append(999999999999999)
B=[]
for i in range(1,35):
    B.append(2**i)
ans=0
for i in range(N):
    if A[N-1-i]==int(A[N-1-i]):
        for j in range(len(B)):
            if A[N-1-i]<B[j]:
                break
        if A[bisect.bisect_left(A,B[j]-A[N-1-i])]==B[j]-A[N-1-i]:
            if bisect.bisect_left(A,B[j]-A[N-1-i])<N-1-i:
                A[bisect.bisect_left(A,B[j]-A[N-1-i])]-=0.1
                A[N-1-i]+=0.1
                ans+=1
print(ans)

Solution (Python):
from collections import Counter
input()
A=list(map(int,input().split()))
A.sort(reverse=True)
C=Counter(A)
ans=0
for a in A:
    if not C[a]:
        continue
    C[a]-=1
    t=2**a.bit_length()-a
    if C[t]:
        C[t]-=1
        ans+=1
print(ans)

Solution (Python):
from collections import Counter
input()
A=list(map(int,input().split()))
A.sort(reverse=True)
C=Counter(A)
ans=0
for a in A:
    if C[a]==0:
        continue
    C[a]-=1
    t=2**a.bit_length()-a
    if C[t]:
        C[t]-=1
        ans+=1
print(ans)

Solution (Python):
def main(l):
    counts = {}
    answer = 0
    for nb in l:
        counts[nb] = counts.get(nb, 0) + 1
    for a in sorted(counts.keys(), reverse=True):
        b = (1 << a.bit_length()) - a
        c_a = counts[a]
        c_b = counts.get(b)
        if c_b:
            if a == b:
                answer += c_a // 2
            else:
                increment = c_a if c_a < c_b else c_b
                counts[a] -= increment
                counts[b] -= increment
                answer += increment

    return answer


if __name__ == '__main__':
    input()
    print(main(map(int, input().split())))

Solution (Python):
input()
nbs = map(int, input().split())

answer = 0
count = {}

for nb in nbs:
    count[nb] = count.get(nb, 0) + 1

for nb in sorted(count.keys(), reverse=True):
    searching = (1 << nb.bit_length()) - nb
    nb_count = count[nb]
    sr_count = count.get(searching, 0)
    if sr_count:
        if nb == searching:
            increment = nb_count // 2
        else:
            increment = nb_count if nb_count < sr_count else sr_count
            count[searching] -= increment
        answer += increment

print(answer)

Solution (Python):

import collections
import math
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
cnter=collections.Counter(A)
ans=0
for a in A:
    inv=2**(int(math.log2(a))+1)
    if cnter[a]==0:
        continue
    if inv==2*a and cnter[inv-a]<=1:
      	continue
    if cnter[inv-a]>0:
        cnter[inv-a]=cnter[inv-a]-1
        cnter[a]=cnter[a]-1
        ans=ans+1
print(ans)

Solution (Python):
from collections import Counter

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

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

Solution (Python):
import bisect
from collections import Counter

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

two_bekis = [2**i for i in range(31)]

ans = 0
cnt = Counter(A)
seta = set(A)
for i, a in enumerate(reversed(A)):
    b = two_bekis[bisect.bisect_right(two_bekis, a)] - a
    if b not in seta:
        continue

    if a == b and cnt[a] >= 2:
        ans += 1
        cnt[a] -= 2
    elif a != b and cnt[a] >= 1 and cnt[b] >= 1:
        ans += 1
        cnt[a] -= 1
        cnt[b] -= 1
print(ans)

Solution (Python):
import bisect
from collections import Counter

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


two_bekis = []
tmp = 1
while tmp < 2*10**9:
    two_bekis.append(tmp)
    tmp *= 2

ans = 0
cnt = Counter(A)
seta = set(A)
for i, a in enumerate(reversed(A)):
    idx = bisect.bisect_right(two_bekis, a)
    two_beki = two_bekis[idx]
    b = two_beki - a
    if b not in seta:
        continue

    if a == b and cnt[a] >= 2:
        ans += 1
        cnt[a] -= 2
    elif a != b and cnt[a] >= 1 and cnt[b] >= 1:
        ans += 1
        cnt[a] -= 1
        cnt[b] -= 1
print(ans)

Solution (Python):
import bisect
from collections import Counter

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


two_bekis = []
tmp = 1
while tmp < 2*10**9:
    two_bekis.append(tmp)
    tmp *= 2

ans = 0
cnt = Counter(A)
seta = set(A)
for i, a in enumerate(reversed(A)):
    idx = bisect.bisect_right(two_bekis, a)
    two_beki = two_bekis[idx]
    b = two_beki - a
    if b not in seta:
        continue

    if a == b and cnt[a] >= 2:
        ans += 1
        cnt[a] -= 2
    elif a != b and cnt[a] >= 1 and cnt[b] >= 1:
        ans += 1
        cnt[a] -= 1
        cnt[b] -= 1
print(ans)

Solution (Python):
import math

N = int(input())
numberList = []
numberList = list(map(int, input().split(" ")))
numberList.sort(reverse=True)
numberDict = {}

for number in numberList:
    if number not in numberDict:
        numberDict[number] = 0
    numberDict[number] += 1

ret = 0

for number in numberList:
    if numberDict[number] > 0:
        numberDict[number] -= 1


        gap = 2 ** (int(math.log(number, 2)) + 1) - number
        if gap in numberDict and numberDict[gap] > 0:
            numberDict[gap] -= 1
            ret += 1

print(ret)

Solution (Python):
from collections import defaultdict

N=int(input())
A=[int(x) for x in input().split()]
A.sort(reverse=True)

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

P2=[]
for i in range(1,32):
  P2.append(2**(32-i))

ans=0

for a in A:
  for b in P2:
    if a >= b or cnt[a] < 1:
      break
    else:
      if (cnt[b-a] > 0 and (b-a) != a) or (cnt[b-a] > 1 and (b-a) == a):
        ans+=1
        cnt[b-a]-=1
        cnt[a]-=1
        break

print(ans)

Solution (Python):
import collections
def hoge(n):
    k = 1    
    while k<=n:
        k*=2
    return k-n
ans = 0
input()
a = [int(x) for x in input().split()]
c = collections.Counter(a)
sa = list(set(a))
sa.sort()
sa.reverse()
for i in range(len(sa)):
    x = sa[i]
    if c[x]<= 0:
        continue    
    y = hoge(x)
    if x==y:
        ans += c[x]//2
    elif c[y]>= 0:
        ans += min(c[x],c[y])
        c[y] -=c[x]
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    d = collections.defaultdict(int)
    for c in a:
        d[c] += 1
    r = 0
    ii = 2**32
    for k in sorted(d.keys(), reverse=True):
        while k < ii // 2:
            ii //= 2
        if k * 2 == ii:
            r += d[k] // 2
        else:
            t = ii - k
            u = min(d[t], d[k])
            r += u
            d[t] -= u
    return r


print(main())

Solution (Python):
from collections import Counter

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

inputs.sort(reverse=True)
counter_inputs = Counter(inputs)
powers_of_two = [2**i for i in range(1, 31)]
ans = 0

for item in inputs:
    if counter_inputs[item] > 0:
        counter_inputs[item] -= 1
    
        while powers_of_two[-1] > 2 * item:
            powers_of_two.pop(-1)
        
        pair = powers_of_two[-1] - item
        if counter_inputs[pair] > 0:
            ans += 1
            counter_inputs[pair] -= 1
    
print(ans)

Solution (Python):

from sys import stdin
import numpy as np
from collections import Counter

d_in = lambda: int(stdin.readline())  
ds_in = lambda: list(map(int, stdin.readline().split()))  

N = d_in()
A_list = np.array(ds_in())
A_list.sort()
EPSILON = 10**(-6)

cand_A = 2 ** (np.log2(A_list + EPSILON).astype(int) + 1) - A_list
idx = np.searchsorted(A_list, cand_A)
A_count = dict(Counter(A_list))

ans = 0
for i in range(N-1, -1, -1):
    if A_count[A_list[i]] <= 0:
        continue
    A_count[A_list[i]] -= 1
    if (A_list[idx[i]] == cand_A[i]) and (A_count[cand_A[i]] > 0):
        ans += 1
        A_count[cand_A[i]] -= 1

print(ans)

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

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

ans = 0
for n in a:
    g = 2 ** n.bit_length()
    s = g - n
    if n == s:
        pair = cnt.get(s, 0) // 2
        ans += pair
        cnt[s] = cnt.get(s, 0) % 2
    else:
        pair = min(cnt.get(n, 0), cnt.get(s, 0))
        ans += pair
        cnt[n] = cnt.get(n, 0) - pair
        cnt[s] = cnt.get(s, 0) - pair
print(ans)

Solution (Python):
from collections import Counter

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

A.sort(reverse=True)
C = Counter(A)
m = 1 << 30
ans = 0

for a in A:
    if C[a] <= 0:
        continue
    C[a] -= 1
    while m > a * 2:
        m >>= 1
    v = m - a
    if v in C and C[v] > 0:
        C[v] -= 1
        ans += 1

print(ans)

Solution (Python):
import collections


def run(N, A):
    cnt = 0
    beki = [2**i for i in range(1, 32)]
    A = sorted(A, reverse=True)
    used = collections.Counter(A)
    for a in A:
        if used[a] == 0:
            continue
        used[a] -= 1
        while beki[-1] > 2*a:
            beki.pop(-1)
        if used[beki[-1] - a] >= 1:
            cnt += 1
            used[beki[-1] - a] -= 1
    return cnt


def main():
    N = int(input())
    A = list(map(int, input().split()))
    print(run(N, A))


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):
    if A[k]==int(A[k]):
        b = 1
        while b <= A[k]:
            b *= 2
        p = bisect.bisect_left(A,b-A[k])
        if p != k and A[p]+A[k] == b:
            ans += 1
            A[k] += 0.9
            A[p] -= 0.9
print(ans)

Solution (Python):
from bisect import bisect
from math import log2
n = int(input())
a = [int(i) for i in input().split()]
a,x,ans = sorted(a),[1]*n,0
for i in range(n-1,-1,-1):
	if x[i]:
		m = 2**(int(log2(a[i]))+1)
		b = bisect(a,m-a[i],hi=i)-1
		if b+1 and a[b]==m-a[i]: x[b],ans,a[b],a[i] = 0,ans+1,a[b]+0.1,a[i]+0.1
print(ans)

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

used = collections.Counter(a)
a.sort()
a.reverse()

two = [2]
i = 0
while two[i]*2 <= 2*10**9:
    two.append(two[i]*2)
    i += 1

counter = 0
for i in range(n):
    if used[a[i]] > 0:
        used[a[i]] -= 1
        while two[-1] > 2*a[i]:
            two.pop(-1)

        if used[two[-1]-a[i]] >= 1:
            counter += 1
            used[two[-1]-a[i]] -= 1

print(counter)

Solution (Python):



from collections import Counter

def  maxCountPair(n_ballCount,a_ballDatas):
	a_ballDatas.sort(reverse=True)
	ballDictBox = Counter(a_ballDatas)
	ballCountRange = range(0,n_ballCount)
	pairCount = 0
	for i in ballCountRange:
		getBallNumber = a_ballDatas[i]
		getBallNumberBin = getBallNumber.bit_length()
		nextTwoPower = 2**getBallNumberBin
		diffNumber = nextTwoPower - getBallNumber
		if ( 1 <= ballDictBox[diffNumber] and 1<= ballDictBox[getBallNumber]):
			if getBallNumber != diffNumber:
				pairCount = pairCount + 1
				ballDictBox[getBallNumber]=ballDictBox[getBallNumber]-1
				ballDictBox[diffNumber] = ballDictBox[diffNumber]-1
			else:
				if 2 <= ballDictBox[diffNumber]:
					pairCount = pairCount + 1
					ballDictBox[diffNumber]=ballDictBox[diffNumber]-2
	answer = pairCount
	return answer


if __name__ == '__main__':
	n_ballCount=int(input())
	a_ballDatas=list((map(int,input().split(" "))))
	solution=maxCountPair(n_ballCount,a_ballDatas)
	print(solution)

Solution (Python):
N = int(input())
A = list(map(int,input().split(" ")))
A.sort()
used = [0] * N
pow2_set = reversed([ 1<<i for i in range(36)])
ans = 0
for pow2 in pow2_set:
    l,r = 0,N-1
    while l < r:
        if A[l] + A[r] < pow2:
            l += 1
        elif A[l] + A[r] == pow2:
            if used[l] == 0 and used[r] == 0:
                ans += 1
                used[l],used[r] = 1,1
            else:
                if used[l] == 1:
                    l += 1
                if used[r] == 1:
                    r -= 1
        else:
            r -= 1
 
print(ans)

Solution (Python):
import sys
import math
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b

def check_t(num):
    t = math.log(num,2)
    return 2**(int(t)+1)



from collections import defaultdict
n = getN()
nums = getlist()
numhash = defaultdict(int)
for i in nums:
    numhash[i] += 1
ans = 0
for num in sorted(numhash.keys(), key=lambda x: -x):
    while(numhash[num] != 0):
        target = (check_t(num)) - num
        if numhash[target]:

            if target == num:
                if numhash[target] >= 2:
                    ans += 1
                    numhash[target] -= 2
                else:
                    numhash[num] = 0
            else:
                if numhash[target] >= 1:
                    ans += 1
                    numhash[target] -= 1
                    numhash[num] -= 1
                else:
                    numhash[num] = 0
        else:
            numhash[num] = 0


print(ans)

Solution (Python):
from collections import defaultdict
import math

n = int(input())
a_list = list(map(int, input().split()))
d = defaultdict(int)

for a in a_list:
  d[a] += 1

a_list = reversed(sorted(list(set(a_list))))
c = 0
for a in a_list:
  m = int(math.log(a, 2))
  x = 2 ** (m+1) - a
  if x == a:
    c += d[a] // 2
    d[a] -= d[a] // 2
  else:
    c += min(d[x], d[a])
    d[x] -= min(d[x], d[a])

print(c)

Solution (Python):
import math
from collections import defaultdict
N = int(input())
A = sorted(int(i) for i in input().split())

d = defaultdict(lambda: 0)
for i in A:
    d[i] += 1

c = 0
for k in sorted(d.keys(), reverse=True):
    l = 2**int(math.log(k, 2) + 1) - k
    v = d[k]
    if k == l:
        c += v // 2
    elif l in d:
        w = d[l]
        if v > w:
            c += w
            d[l] = 0
        else:
            c += v
            d[l] = w-v
print(c)

Solution (Python):
N = int(input())
A_list = list(map(int, input().split()))
two_list = [2 ** i for i in range(32)]

count = 0
items = {}
for a in A_list:
    if a in items.keys():
        items[a] += 1
    else:
        items[a] = 1
A_list.sort(reverse=True)
import bisect

for a in A_list:
    if items[a] >= 1:
        index = bisect.bisect_left(two_list, a)
        for t in two_list[index:]:
            m = t - a
            if m in items.keys():
                if m == a and items[a] >= 2:
                    count += 1
                    items[a] -= 2
                    break

                elif m != a and items[m] >= 1 and items[a] >= 1:
                    count += 1
                    items[a] -= 1
                    items[m] -= 1
                    break
print(count)

Solution (Python):
N = int(input())
A_list = list(map(int, input().split()))
two_list = [2 ** i for i in range(32)]
count = 0
items = {}
for a in A_list:
    if a in items:
        items[a] += 1
 
    else:
        items[a] = 1
A_list.sort(reverse=True)
 
for a in A_list:
    if items[a] >= 1:
 
        for t in two_list:
            m = t -a
            if m in items:
                if m == a and items[a] >= 2:
                    count += 1
                    items[a] -= 1
                    items[m] -= 1
                    break
 
                elif m != a and items[m] >= 1 and items[a] >=1:
                    count += 1
                    items[a] -= 1
                    items[m] -= 1
                    break
print(count)

Solution (Python):
N = int(input())
A_list = list(map(int, input().split()))
two_list = [2 ** i for i in range(32)]

count = 0
items = {}
for a in A_list:
    if a in items:
        items[a] += 1

    else:
        items[a] = 1
A_list.sort(reverse=True)

for a in A_list:
    if items[a] >= 1:
        for t in two_list:
            m = t - a
            if m in items:
                if m == a and items[a] >= 2:
                    count += 1
                    items[a] -= 1
                    items[m] -= 1
                    break

                elif m != a and items[m] >= 1 and items[a] >= 1:
                    count += 1
                    items[a] -= 1
                    items[m] -= 1
                    break
print(count)