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






import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N = I()
A = IL()

dic = DD(int)
for a in A:
  dic[a] += 1
  
kieru = DD(int)

A.sort(reverse = True)

ans = 0
for a in A:
  if kieru[a]:
    kieru[a] -= 1
    continue
  dic[a] -= 1
  if a == (1<<(a.bit_length()-1)):
    if dic[a]:
      kieru[a] += 1
      dic[a] -= 1
      ans += 1
  else:
    b = (1<<a.bit_length()) - a
    if dic[b]:
      kieru[b] += 1
      dic[b] -= 1
      ans += 1
print(ans)

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

def main():
    n = int(input())
    alst = list(map(int, input().split()))
    alst.sort(reverse = True)
    max_a = alst[0]
    dd = defaultdict(int)
    for a in alst:
        dd[a] += 1
    i = 1
    while i <= max_a:
        i *= 2
    ans = 0
    for a in alst:
        if dd[a] <= 0:
            continue
        while i > a * 2:
            i /= 2
        dd[a] -= 1
        num = i - a
        if dd[num]:
            ans += 1
            dd[num] -= 1
    print(ans)
    
main()

Solution (Python):
import sys
from collections import Counter

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    A = sorted(in_nl())[::-1]

    a_cnt = Counter(A)

    ans = 0
    for i in range(N):
        if a_cnt[A[i]] == 0:
            continue
        pow_two = 2 ** A[i].bit_length()
        search = pow_two - A[i]
        a_cnt[A[i]] -= 1
        if a_cnt[search] >= 1:
            ans += 1
            a_cnt[search] -= 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    INF = 10**10
    N = NI()
    a = LI()
    a.sort()
    u = 2 ** 31
    ans = 0
    while u > 2:
        u /= 2
        j = N-1
        for i in range(N):
            if a[i] == INF: continue
            while j > i and a[i] + a[j] > u:
                j -= 1
            if j <= i: break
            if a[i] + a[j] == u:
                ans += 1
                a[i] = a[j] = INF

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

n = int(input())
l = sorted(list(map(int,input().split())))
d = Counter(l)
ans = 0
for i in range(n-1,-1,-1):
    if d[l[i]] == 0:
        continue
    d[l[i]] -= 1
    x = 2**(l[i].bit_length())
    y = x-l[i]
    if d[y] > 0:
        d[y] -= 1
        ans += 1
            
print(ans)

Solution (Python):
from collections import defaultdict
d = defaultdict(int)
n = int(input())
l = sorted(list(map(int,input().split())))
for i in l:
    d[i] += 1

ans = 0
for i in range(n-1,-1,-1):
    if d[l[i]] == 0:
        continue
    x = 2**(l[i].bit_length())
    y = x-l[i]
    if y == l[i]:
        if d[y] >= 2:
            d[y] -= 2
            ans += 1
    else:
        if d[y] > 0:
            d[y] -= 1
            d[l[i]] -= 1
            ans += 1
            
print(ans)

Solution (Python):
from collections import defaultdict

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

cnt = defaultdict(int)

for a in A:
    cnt[a] += 1
res = 0
for x in reversed(A):
    y = (1 << x.bit_length()) - x
    if x == y:
        k = cnt[x]//2
    else:
        k = min(cnt[x], cnt[y])
    res += k
    cnt[x] -= k
    cnt[y] -= k

print(res)

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dic = {}
    for v in a:
        if v in dic:
            dic[v] += 1
        else:
            dic[v] = 1
    key = [v for v in dic.keys()]
    key.sort(reverse=True)
    ans = 0
    for v in key:
        num = dic[v]
        if num > 0:
            for i in reversed(range(1, 32)):
                target = 2**i
                if 2*v < target:
                    continue
                if target < v:
                    break
                u = target - v
                if v == u:
                    z = dic[v]//2
                    ans += z
                    dic[v] -= 2*z
                elif u in dic:
                    x, y = dic[v], dic[u]
                    z = 0
                    if x < y:
                        z = x
                    else:
                        z = y
                    dic[v] -= z
                    dic[u] -= z
                    ans += z
                if dic[v] == 0:
                    break
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from math import log
n = int(input())
A = list(map(int, input().split()))
num = {}
for a in A:
	if a in num:
		num[a] += 1
	else:
		num[a] = 1

ans = 0
cnt = int(log(max(A), 2)) + 5 
for i in range(cnt, 0, -1):
	b = {}
	for x in num:
		if 2 ** i - x in b:
			b[2 ** i - x] += 1
		else:
			b[2 ** i - x] = 1
	for x in num:
		if x in b and num[x] > 0:
			if x * 2 == 2 ** i:
				ans += num[x] // 2
				num[x] %= 2
			else:
				small = min(num[x], num[2 ** i - x])
				ans += small
				num[x] -= small
				num[2 ** i - x] -= small
print(ans)

Solution (Python):
def main():
	from math import log,ceil
	n=int(input())
	a=list(map(int,input().split()))
	num={}
	for x in a:
		if x in num:
			num[x]+=1
		else:
			num[x]=1
	ans=0
	cnt=ceil(log(max(a),2)+1e-7)
	for i in range(cnt,0,-1):
		b=set(2**i-x for x in num)
		for x in num:
			if x in b and num[x]>0:
				if x*2==2**i:
					ans+=num[x]//2
					num[x]%=2
				else:
					small=min(num[x],num[2**i-x])
					ans+=small
					num[x]-=small
					num[2**i-x]-=small
	print(ans)
if __name__ == '__main__':
	main()

Solution (Python):
def main():
	from math import log,ceil
	n=int(input())
	a=list(map(int,input().split()))
	num={}
	for x in a:
		if x in num:
			num[x]+=1
		else:
			num[x]=1
	ans=0
	cnt=ceil(log(max(a),2)+1e-9)+1

	for i in range(cnt,0,-1):
		b={}
		for x in num:
			if 2**i-x in b:
				b[2**i-x]+=1
			else:
				b[2**i-x]=1
		for x in num:
			if x in b and num[x]>0:
				if x*2==2**i:
					ans+=num[x]//2
					num[x]%=2
				else:
					small=min(num[x],num[2**i-x])
					ans+=small
					num[x]-=small
					num[2**i-x]-=small
	print(ans)
if __name__ == '__main__':
	main()

Solution (Python):
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort()
    MAX = A[-1] * 2
    D = Counter(A)
    res = 0
    for i in reversed(range(n)):
        if D[A[i]] == 0:
            continue
        target = 2
        while target <= MAX:
            if D.get(target - A[i], 0) != 0:
                if A[i] != target - A[i]:
                    D[A[i]] -= 1
                    D[target - A[i]] -= 1
                    res += 1
                    break
                else:
                    if D[A[i]] != 1:
                        D[A[i]] -= 2
                        res += 1
                        break
            target *= 2
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import Counter
N=int(input())
A=sorted(map(int,input().split()),reverse=True)
c=Counter(A)
ans=0
for i in range(N):
    if c[A[i]]==0:
        continue
    c[A[i]]-=1
    k=1<<A[i].bit_length()
    v=k-A[i]
    if v in c and c[v]>0:
        ans+=1
        c[v]-=1
print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
from collections import Counter as co
D=co(A)

cnt=0
for i in range(N):
  if D[A[-1-i]]>0:
    D[A[-1-i]]-=1
    d=A[-1-i]
    f=len(bin(d))-2
    e=2**f-d
    if D[e]>0:
      cnt+=1
      D[e]-=1
print(cnt)

Solution (Python):
def main():
  n = int(input())
  a = list(map(int, input().split()))
  
  a.sort()
  
  border = []
  
  key = 2
  for i in range(n):
    while key <= a[i]:
      border.append(i)
      key *= 2
  
  border.append(n)
  border.reverse()
  
  ans = 0
  already = [False]*n
  for v in border:
    index = 0
    for i in range(v-1, -1, -1):
      if already[i]:
        continue
      while index < i and (a[i]+a[index] < key or already[index]):
        index += 1
      if index == i:
        break
      if a[i]+a[index] == key:
        already[i] = True
        already[index] = True
        ans += 1
    
    key //= 2
  
  print(ans)
  
  
if __name__ == "__main__":
  main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter

    n = int(readline())
    a = list(map(int, readline().split()))
    counter = Counter(a)

    keys = list(counter.keys())
    keys.sort(reverse=True)

    ans = 0

    for num1 in keys:
        c1 = counter[num1]
        x = 1
        while x <= num1:
            x *= 2
        num2 = x - num1
        if num1 == num2:
            cnt = c1 // 2
            ans += cnt
            counter[num1] -= cnt * 2
        else:
            c2 = counter[num2]
            cnt = min(c1, c2)
            ans += cnt
            counter[num1] -= cnt
            counter[num2] -= cnt

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
A.sort()
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict 
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache





import bisect as bi
Q=deque(A)
rui=[pow(2,i) for i in range(31)]
ans=0
C=Counter(A)

while Q:
    k=Q.pop()
    if C[k]==0:continue
    for r2 in rui:
        if r2>2*k:break
        if C.get(r2-k,None)==None:continue
        if r2-k==k: 
            if C[k]<=1:continue
        if C[r2-k]==0: continue
        C[r2-k]-=1;C[k]-=1;ans+=1

print(ans)

Solution (Python):
from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MAX_EXP = 30  
    pow2 = [1] * (MAX_EXP + 1)
    for e in range(1, MAX_EXP + 1):
        pow2[e] = 2 * pow2[e - 1]
    counter = defaultdict(int)
    for a in A:
        counter[a] += 1
    DISTINCT_A = list(counter.keys())
    DISTINCT_A.sort(reverse=True)  
    
    
    ans = 0
    for a in DISTINCT_A:
        b = pow2[a.bit_length()] - a
        if counter[b] == 0:
            continue
        cnt = min(counter[a], counter[b])
        ans += cnt
        counter[a] -= cnt
        counter[b] -= cnt
    
    for e in range(MAX_EXP + 1):
        a = pow2[e]
        ans += counter[a] // 2
    print(ans)


if __name__ == '__main__':
    main()

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

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
wait = defaultdict(int)
ans = 0

for Ai in A:
    if wait[Ai]>=1:
        ans += 1
        wait[Ai] -= 1
    else:
        t = 0
    
        while 2**t<=Ai:
            t += 1
    
        wait[2**t-Ai] += 1

print(ans)

Solution (Python):
from collections import Counter
n = int(input())
a = sorted(list(map(int, input().split())))[::-1]
c = Counter(a)
ans = 0
for i in range(n):
    if c[a[i]] > 0:
        m = (1 << a[i].bit_length()) - a[i]
        c[a[i]] -= 1
        if c[m] > 0:
            c[m] -= 1
            ans += 1
print(ans)

Solution (Python):
from collections import Counter

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

C = Counter(A)
A.sort(reverse=True)
ans = 0
for i in range(N):
    x = A[i]
    if C[x] > 0:
        y = 2**x.bit_length() - x
        C[x] -= 1
        if C[y] > 0:
            C[y] -= 1
            ans += 1

print(ans)

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

Solution (Python):
from collections import defaultdict

n = int(input())
A = list(int(x) for x in input().split())

count = defaultdict(int)
for a in A:
    count[a] += 1
A = sorted(set(A))

ans = 0
for a in reversed(A):
    t = a.bit_length()
    pair = 2**t - a
    if pair == a:
        ans += count[a] // 2
        count[a] -= count[a] // 2
    else:
        k = min(count[a], count[pair])
        ans += k
        count[a] -= k
        count[pair] -= k

print(ans)

Solution (Python):
from collections import defaultdict
import sys

input = sys.stdin.buffer.readline

n = int(input())
A = list(map(int, input().split()))
jisho = defaultdict(int)
for a in A:
    jisho[a] += 1
A.sort()
ans = 0
for i in range(n - 1, -1, -1):
    num = A[i]
    if jisho[num] == 0:
        continue
    jisho[num] -= 1
    temp = num // (num & -num)
    keta = temp.bit_length()
    kouho = 1
    for i in range(1, keta):
        if (temp >> i) & 1 == 0:
            kouho += 1 << i
    kouho *= num & -num
    if jisho[kouho] > 0:
        
        jisho[kouho] -= 1
        ans += 1
print(ans)

Solution (Python):
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
ca=dict(Counter(a))
a.sort()
ans=0
for i in range(n):
  x=a[-1-i]
  tmp=pow(2,len(bin(x))-2)-x
  if x==tmp:
    if ca[x]>=2:
      ca[x]-=2
      ans+=1
  elif ca[x] and tmp in ca and ca[tmp]>0:
    ans+=1
    ca[tmp]-=1
    ca[x]-=1

print(ans)

Solution (Python):
N = int(input())
As = sorted(map(int, input().split()))

used = [False] * N

ans = 0
for i in range(31, 0, -1):
    power_of_two = 1 << i
    l = 0
    r = N - 1
    while True:
        while l < N and used[l]:
            l += 1
        while r >= 0 and used[r]:
            r -= 1
        if l >= r:
            break

        if As[l] + As[r] == power_of_two:
            used[l] = True
            used[r] = True
            l += 1
            r -= 1
            ans += 1
        elif As[l] + As[r] < power_of_two:
            l += 1
        else:
            r -= 1

print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a.sort()
m = max(a)*2
from collections import Counter, defaultdict
c = Counter(a)
kvs = [(k,v) for k,v in c.items()]
kvs.sort(reverse=True)
c = {}
for k,v in kvs:
    c[k] = v
ans = 0
vs = []
i = 2
while True:
    if i<=m:
        vs.append(i)
        i *= 2
    else:
        break
vs = vs[::-1]

for k in c:
    for v in vs:
        if k<v and v-k in c and c[v-k]>0:
            if k==v-k:
                ans += c[k]//2
                c[k] = c[k]%2
            elif c[k]<=c[v-k]:
                ans += c[k]
                c[v-k] -= c[k]
                c[k] = 0
            else:
                ans += c[v-k]
                c[k] -= c[v-k]
                c[v-k] = 0
print(ans)

Solution (Python):
import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()
A = inl()
A.sort()


def solve():
    ac = collections.Counter(A)
    num_pairs = 0
    for i in range(N - 1, 0, -1):
        x = A[i]
        if ac[x] <= 0:
            continue
        p = 1
        while p <= x:
            p <<= 1
        j = bisect.bisect_left(A, p - x, 0, i)
        if j >= i:
            continue
        y = A[j]
        if x + y != p:
            continue
        ac[x] -= 1
        if ac[y] <= 0:
            continue
        ac[y] -= 1
        num_pairs += 1
    return num_pairs


print(solve())

Solution (Python):
from collections import defaultdict
from bisect import bisect_right

balls_count = defaultdict(int)

N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
ans = 0
beki_list = [pow(2, i) for i in range(1, 32)]
for a in A:
    balls_count[a] += 1

for a in A:
    if balls_count[a] == 0:
        continue
    balls_count[a] -= 1
    index = bisect_right(beki_list, a)
    pair = beki_list[index] - a
    if balls_count[pair] > 0:
        balls_count[pair] -= 1
        ans += 1
print(ans)

Solution (Python):
from collections import defaultdict
from bisect import bisect_right

balls_count = defaultdict(int)

N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
ans = 0
beki_list = [pow(2, i) for i in range(1, 32)]
for a in A:
    balls_count[a] += 1

for a in A:
    if balls_count[a] == 0:
        continue
    balls_count[a] -= 1
    index = bisect_right(beki_list, a)
    pair = beki_list[index] - a
    if balls_count[pair] > 0:
        balls_count[pair] -= 1
        ans += 1
print(ans)

Solution (Python):
from collections import defaultdict

n = int(input())
a = list(map(int,input().split()))
a2 = list(set(a))
a2.sort(reverse=True)

d = defaultdict(int)
for i in a:
    d[i] += 1

ans = 0
for i in a2:
    next = 2**(i-1).bit_length()
    if(i==next):
        ans += d[i]//2
    else:
        pair = min(d[i],d[next-i])
        d[next-i] -= pair
        ans += pair
print(ans)

Solution (Python):

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
ans = 0

D = defaultdict(int)
for x in A:
    D[x] += 1
A.sort(reverse=True)

for x in A:
    for i in range(1, 31):
        if D[x] > 0:
            if 2**i-x in D.keys() and D[2**i-x] > 0:
                if 2**(i-1) != x:
                    ans += 1
                    D[x] -= 1
                    D[2**i-x] -= 1
for i in range(31):
    ans += D[2**i]//2
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline









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

from collections import defaultdict

balls_count = defaultdict(int) 

for a in A:
  balls_count[a] += 1

A = sorted(A, reverse = True)

def get_pair_num(x): 
  tar = 2
  while tar < x:
    tar *= 2
  if tar == x:
    return tar
  return tar - x

ans = 0
for ball in A:
  if balls_count[ball] == 0: 
    continue
  
  
  balls_count[ball] -= 1
  pair = get_pair_num(ball)
  if balls_count[pair] > 0:
    ans += 1
    balls_count[pair] -= 1

print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline









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

from collections import defaultdict

balls_count = defaultdict(int) 

import heapq as hq
balls_q = [] 

for a in A:
  balls_count[a] += 1
  hq.heappush(balls_q, -a)

def get_pair_num(x): 
  tar = 2
  while tar < x:
    tar *= 2
  if tar == x:
    return tar
  return tar - x

ans = 0
while balls_q:
  ball = -(hq.heappop(balls_q))
  if balls_count[ball] == 0: 
    continue
  
  
  balls_count[ball] -= 1
  pair = get_pair_num(ball)
  if balls_count[pair] > 0:
    ans += 1
    balls_count[pair] -= 1
  

print(ans)

Solution (Python):
from collections import defaultdict
dic = defaultdict(int) 

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

for i in A:
  dic[i] +=1

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

L = [[] for _ in range(N)]
for i in range(N):
  for t in beki:
    now = t-A[i]
    if A[i] == now and dic[now] >=2:
      L[i].append(now)
    elif A[i] != now and now>0 and now in dic:
      L[i].append(now)
  L[i].append(A[i]) 




ans = 0
for i in range(N):
  now = L[i].pop()
  
  for num in L[i]:
    if num in dic:
      if num == now and dic[now] > 1:
        dic[num] -=2
        ans += 1
        break
      elif num != now and dic[num] > 0 and dic[now] > 0:
        dic[num] -= 1
        dic[now] -= 1
        ans += 1
        break

print(ans)

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


from bisect import bisect_left, bisect_right





input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def solve():
    n = getN()
    nums = getList()
    stock = defaultdict(int)
    for num in nums:
        stock[num] += 1

    
    ans = 0
    for i in range(32, -1, -1):
        tgt = 2 ** i
        
        d = defaultdict(int)
        for num in nums:
            d[tgt - num] += 1
        
        for dk in d.keys():
            if dk * 2 == tgt:
                a = stock[dk] // 2
                ans += a
                stock[dk] -= 2 * a
            else:
                
                if dk in stock:
                    
                    
                    a = min(stock[tgt - dk], stock[dk])
                    ans += a
                    stock[dk] -= a
                    stock[tgt - dk] -= a


    print(ans)
def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    
    solve()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a.sort()
a.reverse()
s={}
for i in a:
  if i in s:
    s[i]+=1
  else:
    s[i]=1
i=0
current=40
l=0
ans=0
while current!=0 and i<n:
  l=i
  while a[i]>=pow(2,current-1):
    i+=1
    if i==n:
      break
  r=i
  for j in range(l,r):
    if s[a[j]]==0:
      continue
    if pow(2,current)-a[j] in s:
      if a[j]==pow(2,current-1):
        if s[a[j]]>=2:
          ans+=1
          s[a[j]]-=2
      else:
        if s[pow(2,current)-a[j]]>0:
          s[pow(2,current)-a[j]]-=1
          s[a[j]]-=1
          ans+=1
  current-=1
print(ans)

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



A.sort()
cnt = Counter(A)
keys = sorted(cnt.keys(), reverse=True)

ans = 0
for a in keys:
    p = len(bin(a)) - 2
    t = (1 << p) - a
    if a == t:
        d = cnt[a]//2
        ans += d
        cnt[a] -= 2*d
        continue
    if t in cnt:
        d = min(cnt[t],cnt[a])
        ans += d
        cnt[t] -= d
        cnt[a] -= d
print(ans)

Solution (Python):
import bisect

n = int(input())
a = sorted(list(map(int, input().split())))

cnt = {}
for x in a:
    if x in cnt:
        cnt[x] += 1
    else:
        cnt[x] = 1

ans = 0
for i in range(n - 1, -1, -1):
    for d in range(30, -1, -1):
        k = bisect.bisect_left(a, (1 << d) - a[i])
        if k < n and a[i] + a[k] == (1 << d) and (a[i] == a[k] and cnt[a[i]] >= 2 or a[i] != a[k] and cnt[a[i]] >= 1 and cnt[a[k]] >= 1):
            ans += 1
            cnt[a[i]] -= 1
            cnt[a[k]] -= 1

print(ans)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = list(map(int,ipt().split()))
    a.sort(reverse=True)
    d = defaultdict(int)
    ans = 0
    for i in a:
        if d[i]:
            ans += 1
            d[i] -= 1
        else:
            nl = len(format(i,"b"))
            d[(i^(2**(nl)-1))+1] += 1

    print(ans)
    return

if __name__ == '__main__':
    main()

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = list(map(int,ipt().split()))
    a.sort(reverse=True)
    d = defaultdict(int)
    ans = 0
    for i in a:
        if d[i]:
            ans += 1
            d[i] -= 1
        else:
            nl = len(format(i,"b"))
            d[(i^(2**(nl)-1))+1] += 1

    print(ans)
    return

if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
import bisect

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

    A.sort()
    counter = Counter(A)
    ch = [True] * n

    beki = []
    c = 1
    for _ in range(31):
        beki.append(c)
        c *= 2

    
    ans = 0
    for i in range(n-1,-1,-1):
        a = A[i]
        j = bisect.bisect_right(beki,a)
        t = beki[j] - a
        
        if t == a:
            m = counter[a]//2
        elif t < a:
            m = min(counter[a],counter[t])

        counter[a] -= m
        counter[t] -= m
        ans += m
    print(ans)

main()

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

from collections import defaultdict
d = defaultdict(int)

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

ans=0
for num in sorted(d,reverse=True):
    while d[num]>=1:
        d[num]-=1

        now=1
        while now<=num:
            now*=2

        cand = now - num
        if d[cand]>=1:
            d[cand]-=1
            ans+=1
        else:
            break
print(ans)

Solution (Python):
n=int(input())
l=sorted(list(map(int,input().split())),reverse=1)
from collections import Counter as co
d=co(l)
ans=0
for i in l:
    x=pow(2,i.bit_length())-i

    if d[i]>0 and x in d and d[x]>0:
        if x!=i:d[x]-=1;ans+=1;d[i]-=1
        elif d[i]>=2:d[i]-=2;ans+=1
print(ans)

Solution (Python):
from heapq import heappush, heappop, heapify
from bisect import bisect_right

pow2 = [2]
for i in range(29):
  pow2.append(pow2[-1]*2)

N = int(input())
A = list(map(int, input().split()))
d = {}
for a in A:
  if a in d:
    d[a] += 1
  else:
    d[a] = 1

A = [-a for a in A]
heapify(A)
ans = 0
while A:
  a = - heappop(A)
  if d[a] == 0:
    continue
  pair = pow2[bisect_right(pow2, a)] - a
  if a == pair:
    if d[a] >= 2:
      d[a] -= 2
      ans += 1
  elif pair in d and d[pair] > 0:
    ans += 1
    d[pair] -= 1
    d[a] -= 1

print(ans)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
cnt=0
maxa=max(a)
while 2**cnt<2*maxa:
    cnt+=1
    

lsta=[0]*n
ans=0
for i in range(1,cnt+1)[::-1]:
    dic=defaultdict(list)
    for j in range(n):
        if 2**i>a[j] and lsta[j]==0:
            if dic[a[j]]!=[]:
                lsta[j]=-1
                lsta[dic[a[j]].pop()]=-1
                ans+=1
            else:
                dic[2**i-a[j]].append(j)
    


print(ans)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
cnt=0
maxa=max(a)
while 2**cnt<2*maxa:
    cnt+=1
    

lsta=[0]*n
for i in range(1,cnt+1)[::-1]:
    dic=defaultdict(list)
    for j in range(n):
        if 2**i>a[j] and lsta[j]==0:
            if dic[a[j]]!=[]:
                lsta[j]=-1
                lsta[dic[a[j]].pop()]=-1
            else:
                dic[2**i-a[j]].append(j)
    

ans=-sum(lsta)//2
print(ans)