You are given an array A, consisting of N distinct integers.  
Calculate number of pairs (i,j) (1 ≤ i < j ≤ N), such that 2 \cdot (A_{i} \oplus A_{j}) = A_{i} + A_{j}, where \oplus denotes [bitwise XOR].

------ Input Format ------ 

- The first line contains two integers N - the size of the array. 
- The second line contains N space-separated integers A_{1}, \ldots, A_{N} - the elements of the array A.

------ Output Format ------ 

For each test case, output the number of pairs satisfying constraints.

------ Constraints ------ 

$2 ≤ N ≤ 10^{6}$
$1 ≤ A_{i} ≤ 2^{60}-1$

------ subtasks ------ 

Subtask $1$ (20 points): $2 ≤ N ≤ 2000$
Subtask $2$ (40 points): $1 ≤ A_{i} ≤ 2^{20}-1$
Subtask $3$ (40 points): Original constraints.

----- Sample Input 1 ------ 
4
1 2 3 6

----- Sample Output 1 ------ 
2

----- explanation 1 ------ 
There are $2$ pairs $(i,j)$ satisfying all the conditions.
- $(i,j)= (1, 3)$. Thus, $2\cdot (A_{1}\oplus A_{3}) = 2\cdot (1\oplus 3) = 2\cdot 2 = 4$. Also, $A_{1}+A_{3} = 1+3 = 4$.
- $(i,j)= (2, 4)$. Thus, $2\cdot (A_{2}\oplus A_{4}) = 2\cdot (2\oplus 6) = 2\cdot 4 = 8$. Also, $A_{2}+A_{4} = 2+6 = 8$.

----- Sample Input 2 ------ 
5
4 3 9 7 1
----- Sample Output 2 ------ 
1
----- explanation 2 ------ 
There is only one pair $(i,j)$ satisfying all the conditions:
- $(i,j) = (2, 5)$. Thus, $2\cdot (A_{2}\oplus A_{5}) = 2\cdot (3\oplus 1) = 2\cdot 2 = 4$. Also, $A_{2}+A_{5} = 3+1 = 4$.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Mathematics


Solutions:
def patt(n):
	s = format(n, 'b')[1:]
	i = len(s) - 1
	while i >= 0:
		if s[i] == '1':
			if i - 1 < 0:
				return False
			i -= 2
		else:
			i -= 1
	return True

def rev(n):
	s = format(n, 'b')[1:]
	ans = ''
	i = len(s) - 1
	while i >= 0:
		if s[i] == '1':
			if s[i - 1] == '1':
				ans = '01' + ans
			else:
				ans = '11' + ans
			i -= 2
		else:
			ans = '0' + ans
			i -= 1
	ans = '11' + ans
	return int(ans, 2)
n = int(input())
li = list(map(int, input().split()))
li.sort()
mapp = {}
ans = 0
for i in range(len(li) - 1, -1, -1):
	p = patt(li[i])
	if p and rev(li[i]) in mapp:
		ans += 1
	mapp[li[i]] = True
print(ans)


def do_bitwise_xor(x, y):
	return (x | y) & (~x | ~y)

def split_list_to_even_odd(A: list):
	A_EVEN = []
	A_ODD = []
	for item in A:
		if item % 2 == 0:
			A_EVEN.append(item)
		else:
			A_ODD.append(item)
	return (A_EVEN, A_ODD)

def get_xor_times_two_is_sum_count(A: list):
	length = len(A)
	count = 0
	if length == 0:
		return count
	for i in range(length):
		for j in range(i + 1, length):
			if 2 * do_bitwise_xor(A[i], A[j]) == A[i] + A[j]:
				count += 1
	return count

def xor2ptnr(val):
	sb = ['0'] + list(bin(val)[2:])
	sx = len(sb)
	while sx:
		sx -= 1
		if sb[sx] == '1':
			sx -= 1
			sb[sx] = '1' if sb[sx] == '0' else '0'
	return int(''.join(sb), 2)
N = int(input())
Ays = set(map(int, input().split()))
print(len(Ays.intersection((xor2ptnr(a) for a in Ays if not '1' in bin(a).rsplit('11')[-1]))))


from sys import stdin
from functools import lru_cache
input = stdin.readline

def xor2ptnr_1(inpstr):
	val = int(inpstr)
	if '1' in f'{val:b}'.rsplit('11', maxsplit=1)[-1]:
		return val
	bit = 1
	while bit <= val:
		if bit & val:
			bit <<= 1
			val ^= bit
		bit <<= 1
	return val
N = int(input())
Ays = set(map(xor2ptnr_1, input().split()))
print(N - len(Ays))


from sys import stdin
from functools import lru_cache
input = stdin.readline

def xor2ptnr_1(inpstr):
	val = int(inpstr)
	sb = f'0{val:b}'.rsplit('11')
	if '1' in sb[-1]:
		return val
	return int('01'.join((s.replace('01', '11') for s in sb)), 2)
N = int(input())
Ays = set(map(xor2ptnr_1, input().split()))
print(N - len(Ays))


from sys import stdin
from functools import lru_cache
input = stdin.readline

def xor2ptnr(val):
	sb = f'0{val:b}'.rsplit('11')
	return int('01'.join((s.replace('01', '11') for s in sb)), 2)
N = int(input())
Ays = set(map(int, input().split()))
print(len(Ays.intersection((xor2ptnr(a) for a in Ays if not '1' in bin(a).rsplit('11', maxsplit=1)[-1]))))


from sys import stdin
from functools import lru_cache
input = stdin.readline

def xor2ptnr(val):
	sb = ['0'] + list(bin(val)[2:])
	sx = len(sb)
	while sx:
		sx -= 1
		if sb[sx] == '1':
			sx -= 1
			sb[sx] = '1' if sb[sx] == '0' else '0'
	return int(''.join(sb), 2)
N = int(input())
Ays = set(map(int, input().split()))
print(len(Ays.intersection((xor2ptnr(a) for a in Ays if not '1' in bin(a).rsplit('11')[-1]))))


from sys import stdin
from functools import lru_cache
input = stdin.readline

def xor2ptnr(val):
	sb = ['0'] + list(bin(val)[2:])
	sp = []
	while sb:
		if sb.pop() == '0':
			sp.append('0')
		else:
			sp.append('1')
			if sb.pop() == '0':
				sp.append('1')
			else:
				sp.append('0')
	return int(''.join(reversed(sp)), 2)
N = int(input())
Ays = set(map(int, input().split()))
print(len(Ays.intersection((xor2ptnr(a) for a in Ays))) // 2)