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

import copy
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
b = {}
for c in a:
    try:
        b[c] += 1
    except:
        b[c] = 1


pow2 = 1
while pow2 <= a[0]:
    pow2 *= 2

cnt = 0
for aa in a:
    while  aa < (pow2//2):
        pow2 //= 2
    v = aa
    rem = pow2 - aa
    if (not v in b) or (not rem in b):
        continue

    if rem != v and (b[v] > 0 and b[rem] > 0):
        # hit = min(b[v], b[rem])
        cnt += 1
        b[v] -= 1
        b[rem] -= 1
    else:
        cnt += 1
        b[v] -= 2

print(cnt)



# b = {}
# c = {}
# # print(a)
# for e,i in enumerate(a):
#     b[i] = (e, [(x[0]+e+1, x[1]) for x in enumerate(a[e+1:])])

# # print(b)
# for be in b: # (3, (0, [(1,5),...]) in [3,5,..]
#     for j in b[be][1]:
#         try:
#             if (not (b[be][0], j[0]) in c[be+j[1]]):
#                 # c[be + j[1]].append(b[be][0])
#                 # c[be + j[1]].append(j[0])
#                 c[be+j[1]].append((b[be][0], j[0]))
#         except:
#             c[be + j[1]]  = [(b[be][0], j[0])]
#             # c[be + j[1]].append(b[be][0])
#             # c[be + j[1]].append(j[0])


# # print("c: ", c)
# d= []

# twopowerlist = [2**p for p in range(30)]
# for n in twopowerlist:
#     try:
#         # print(n, c[n])
#         # d[n] = len(c[n])//2

#     except:




# for p in [x for y in d[0] for x in y]:
#     # print("p:",  p)
#     for e,q in enumerate(d[1:]):
#         for j in q:

#                 try:

#                 except:


# # print(d)
# print(len(d[0]))






###########################3



# b = {}
# c = {}
# for e,i in enumerate(a):
#     b[i] = [copy.deepcopy(a)[e+1:], 1]
#     c[i] = 1

# for be in b:
#     for j in b[be][0]:
#         try:
#             c[j+be] += 1
#         except:
#             c[j+be] = 1



# for n in twopowerlist:
#     try:

#     except:

# print("list: ", c)
# print(sum)


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

b = {}
for c in a:
    try:
        b[c] += 1
    except:
        b[c] = 1


pow2 = 1
while pow2 <= a[0]:
    pow2 *= 2

cnt = 0
for aa in a:
    while  aa < (pow2//2):
        pow2 //= 2
    
    v = aa
    rem = pow2 - aa
    
    if (not v in b) or (not rem in b):
        continue

    if rem != v and (b[v] > 0 and b[rem] > 0):
        hit = min(b[v], b[rem])
        cnt += hit
        b[v] -= hit
        b[rem] -= hit
    elif rem == v and b[v] > 1:
        cnt += b[v]//2
        b[v] = b[v]%2

print(cnt)



# b = {}
# c = {}
# # print(a)
# for e,i in enumerate(a):
#     b[i] = (e, [(x[0]+e+1, x[1]) for x in enumerate(a[e+1:])])

# # print(b)
# for be in b: # (3, (0, [(1,5),...]) in [3,5,..]
#     for j in b[be][1]:
#         try:
#             if (not (b[be][0], j[0]) in c[be+j[1]]):
#                 # c[be + j[1]].append(b[be][0])
#                 # c[be + j[1]].append(j[0])
#                 c[be+j[1]].append((b[be][0], j[0]))
#         except:
#             c[be + j[1]]  = [(b[be][0], j[0])]
#             # c[be + j[1]].append(b[be][0])
#             # c[be + j[1]].append(j[0])


# # print("c: ", c)
# d= []

# twopowerlist = [2**p for p in range(30)]
# for n in twopowerlist:
#     try:
#         # print(n, c[n])
#         # d[n] = len(c[n])//2

#     except:




# for p in [x for y in d[0] for x in y]:
#     # print("p:",  p)
#     for e,q in enumerate(d[1:]):
#         for j in q:

#                 try:

#                 except:


# # print(d)
# print(len(d[0]))






###########################3



# b = {}
# c = {}
# for e,i in enumerate(a):
#     b[i] = [copy.deepcopy(a)[e+1:], 1]
#     c[i] = 1

# for be in b:
#     for j in b[be][0]:
#         try:
#             c[j+be] += 1
#         except:
#             c[j+be] = 1



# for n in twopowerlist:
#     try:

#     except:

# print("list: ", c)
# print(sum)

Verdicts: Wrong Answer

Accepted