Read problem statements in [Bengali], [Russian], [Mandarin] and [Vietnamese] as well.

You are given an array A of N non-negative integers, where N is odd. Find the minimum non-negative integer x that satisfies the equation

(A_{1} + x) \oplus (A_{2} + x) \oplus \dots \oplus (A_{N} + x) = 0

where \oplus denotes the [bitwise XOR operation]. If no such x exists, print -1.

Note: The input of this problem is large, so use fast input/output methods.

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

- First line of the input contains a single integer T, the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N, denoting the size of the array A.
- The second line of each test case contains N space-separated non-negative integers A_{1}, A_{2} \dots A_{N}.

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

For each test case, print a single line containing one integer. If there does not exist any non-negative integer x that satisfies the given equation, print -1. Otherwise, print the minimum value of x that satisfies the given equation.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{6}$
$0 ≤ A_{i} ≤ 10^{18}$
- The value of $N$ is guaranteed to be odd.
- Sum of $N$ over all test cases is less than or equal to $10^{6}$.

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

Subtask 1 (20 points):
$1≤ T≤ 10^{3}$
$1≤ N ≤ 10^{3}$
$0≤ A_{i} ≤ 10^{3}$
The value of $N$ is guaranteed to be odd.
Sum of $N$ over all test cases is less than or equal to $10^{3}$.

Subtask 2 (80 points):
Original constraints

----- Sample Input 1 ------ 
4
3
2 4 5
3
0 0 0
3
1 1 1
3
1 1 2

----- Sample Output 1 ------ 
1
0
-1
-1

----- explanation 1 ------ 
Test case 1:

We have to find minimum non-negative integer $x$ such that 
$$(2 + x) \oplus (4 + x) \oplus (5 + x) = 0$$
Let $f(x) = (2 + x) \oplus (4 + x) \oplus (5 + x)$.
- For $x = 0$, we have
$$f(0) = (2 + 0) \oplus (4 + 0) \oplus (5 + 0) = 2\oplus 4\oplus 5 = 3$$
- For $x = 1$, we have
$$f(1) = (2 + 1) \oplus (4 + 1) \oplus (5 + 1) = 3\oplus 5\oplus 6 = 0$$

Therefore, $x = 1$ is the minimum non-negative integer that satisfies the given equation.

Test case 2:

We have to find minimum non-negative integer $x$ such that 
$$(0 + x) \oplus (0 + x) \oplus (0 + x) = 0$$
i.e. $x \oplus x \oplus x = 0$. But since $0 \oplus 0 \oplus 0 = 0$, it follows that $x = 0$ is the minimum non-negative integer that satisfies the given equation.

Test case 3:

We have to find minimum non-negative integer $x$ such that 
$$(1 + x) \oplus (1 + x) \oplus (1 + x) = 0$$
But $a \oplus a = 0$ and $0 \oplus a = a$ for any non-negative integer $a$. It follows that 
$$(1 + x) \oplus (1 + x) \oplus (1 + x) = 0 \oplus (1 + x) = 1 + x$$

This implies that $x$ satisfies the given equation if and only if it satisfies $1 + x = 0$ if and only if $x = -1$. But $-1$ is a negative integer and therefore, there does not exist any $x$ that satisfies the given equation.

Test case 4:

We have to find minimum non-negative integer $x$ such that 
$$(1 + x) \oplus (1 + x) \oplus (2 + x) = 0$$
It follows that 
$$(1 + x) \oplus (1 + x) \oplus (2 + x) = 0 \oplus (2 + x) = 2 + x$$

This implies that $x$ satisfies the given equation if and only if it satisfies $2 + x = 0$, which can only happen if $x = -2$. But $-2$ is a negative integer and therefore, there does not exist any non-negative $x$ that satisfies the given equation, hence we output $-1$.

Difficulty: HARD
Tags: Bit manipulation

Mathematics
Skill types: Bit manipulation

Starter code:

Solutions:
import numpy as np

def xor(a):
	ans = 0
	for i in a:
		ans = ans ^ i
	return ans

def p2(n):
	ans = 0
	while n % 2 == 0:
		n = n // 2
		ans += 1
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	a = np.array(a)
	m = max(a)
	x = 0
	tmp = xor(a)
	while tmp != 0:
		tmp2 = int(2 ** p2(tmp))
		a = a + tmp2
		x = x + tmp2
		if x > m:
			x = -1
			break
		tmp = xor(a)
	print(x)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	nn = max(a)
	if n <= 1000 and nn <= 1000:
		f = 1
		for i in range(n):
			ans = i + a[0]
			for j in range(1, n):
				ans = ans ^ i + a[j]
			if ans == 0:
				print(i)
				f = 0
				break
		if f:
			print(-1)
	else:
		z = 0
		u = a[0]
		c = 0
		for i in range(n):
			if i == 0:
				z += 1
			if i == u:
				c += 1
		if z == n:
			print(0)
		elif c == n:
			print(-1)
		else:
			tmp = a[0]
			for ii in range(1, n):
				tmp = tmp ^ a[ii]
			if tmp == 0:
				print(0)
			else:
				t = bin(tmp)
				t = t[2:]
				t = t[::-1]
				tn = len(t)
				m = max(a)
				b = bin(m)
				b = b[2:]
				m = len(b)
				mm = m

				def xor(aa, x):
					ans = aa[0] + x
					aa[0] = aa[0] + x
					for i in range(1, n):
						ans = ans ^ aa[i] + x
						aa[i] = aa[i] + x
					return (ans, aa)
				i = 0
				ans = 0
				f = 1
				while i <= mm and m <= mm:
					if t[i] == '1':
						(xx, a) = xor(a, 1 << i)
						ans += 1 << i
						i += 1
						if xx == 0:
							print(ans)
							f = 0
							break
						else:
							t = bin(xx)
							t = t[2:]
							t = t[::-1]
							m = len(t)
					else:
						i += 1
				if f:
					print(-1)


T = int(input())
import numpy as np
for _ in range(T):
	N = int(input())
	A = np.array(list(map(int, input().split())))
	j = 0
	mans = []
	old_sam = 0
	for j in range(61):
		oddsum = 0
		jor = np.sum(A) % 2
		mans.append(jor)
		A = A + jor >> 1
		if not any(A) > 0:
			break
	if any(A) > 0:
		print(-1)
	else:
		ans = 0
		mans.reverse()
		for man in mans:
			ans = ans * 2 + man
		print(ans)


from math import log

def SolveE():
	(x, mx) = ('', len(bin(max(A))[1:]))
	for pos in range(mx + 1):
		(xi, res) = (int(x, 2) if len(x) else 0, 0)
		for a in A:
			res ^= a + xi
		x = '1' + x if res % 2 ** (pos + 1) else '0' + x
	return -1 if x[0] == '1' else int(x, 2)
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	print(SolveE())


def solve(A):
	(x, mx) = ('', len(bin(max(A))[1:]))
	for pos in range(mx + 1):
		(xi, res) = (int(x, 2) if len(x) else 0, 0)
		for a in A:
			res ^= a + xi
		x = '1' + x if res % 2 ** (pos + 1) else '0' + x
	return -1 if x[0] == '1' else int(x, 2)
As = []
for _ in range(int(input())):
	N = int(input())
	As.append([int(x) for x in input().split()])
for A in As:
	print(solve(A))


t = int(input())

def isbit(n, i):
	b = bin(n)[2:]
	if len(b) < i:
		return False
	if int(b[-i]):
		return True
	else:
		return False

def xorsum(l, x):
	xum = 0
	for i in l:
		xum ^= i + x
	return xum

def do(l):
	x = 0
	c = xorsum(l, 0)
	cb = bin(c)[2:]
	k = bin(max(l))[2:]
	for i in range(1, max(len(k) + 1, len(cb) + 2)):
		if isbit(xorsum(l, x), i):
			x += 2 ** (i - 1)
	if xorsum(l, x) != 0:
		print(-1)
		return
	print(x)
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	do(l)


def Solve():

	def calc(pos, ans):
		(tmp, x) = (0, int('1' + ans, 2))
		for a in A:
			tmp ^= a + x
		return '1' + ans if bin(tmp)[2:][::-1].ljust(mx, '0')[pos] == '0' else '0' + ans
	mx = len(bin(max(A))[2:])
	ans = ''
	for pos in range(mx + 1):
		ans = calc(pos, ans)
	if int(ans, 2) >= 2 ** mx:
		return -1
	else:
		return int(ans, 2)
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	print(Solve())


import numpy as np
import sys

def compute(input_arr):
	arr = np.array(input_arr)
	ans = 0
	bit_shift = 0
	carry = np.zeros(len(arr), dtype=int)
	while np.count_nonzero(arr) > 0:
		last_bits = arr % 2
		adder_bit = np.count_nonzero(last_bits ^ carry) % 2
		ans += adder_bit << bit_shift
		carry = last_bits * adder_bit | last_bits * carry | adder_bit * carry
		bit_shift += 1
		arr = arr // 2
	if np.bitwise_xor.reduce(np.array(input_arr) + ans) != 0:
		return -1
	return ans
t = int(sys.stdin.readline())
for t_itr in range(t):
	n = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().strip().split()))
	sys.stdout.write(str(compute(arr)) + '\n')


t = int(input())

def func(a):
	ans = 0
	xor = 0
	for _ in range(64):
		for c in a:
			xor = xor ^ c + ans
		if xor == 0:
			return ans
		s = '{0:b}'.format(xor)
		for (i, c) in enumerate(s[::-1]):
			if int(c) == 1:
				ans += 2 ** i
				break
		xor = 0
	return -1
for zzzz in range(t):
	n = input()
	a = [int(x) for x in input().split()]
	print(func(a))


def getAns(entries):
	xorVal = 0
	answer = 0
	for num in entries:
		xorVal ^= num
	index = 0
	maxVal = max(entries)
	while xorVal != 0:
		if maxVal < 1 << index:
			break
		if xorVal & 1 << index:
			answer += 1 << index
		index += 1
		xorVal = 0
		for num in entries:
			xorVal ^= num + answer
	if xorVal != 0:
		return -1
	return answer

def main():
	t = int(input())
	for _ in range(t):
		_ = int(input())
		entries = list(map(int, input().split()))
		print(getAns(entries))
main()


def binary(c):
	return '{0:b}'.format(int(c))

def find_one(a):
	one_index = 0
	dup = a
	while 1:
		if dup % 10 == 1:
			return one_index
		else:
			one_index += 1
			dup = dup // 10
	return None

def xor(n, arr, i):
	xor_val = arr[0] + i
	for l in range(1, n):
		xor_val = xor_val ^ arr[l] + i
	return xor_val

def correct(n, arr):
	maximum = max(arr)
	bin_max = binary(maximum)
	len_bin_max = len(bin_max)
	ans = 0
	jump = 0
	counter = 0
	while counter < len_bin_max:
		counter += 1
		xor_val = xor(n, arr, jump)
		if xor_val == 0:
			print(ans)
			return 0
		else:
			bin = binary(xor_val)
			bin = int(bin)
			one = find_one(bin)
			jump += 2 ** one
			ans += 2 ** one
	print(-1)
	return 0
t = int(input())
for l in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	correct(n, arr)


from sys import stdin
from collections import Counter

def val_xor(vals, bits):
	Cval = Counter(vals)
	red = (v for (v, f) in Cval.items() if f % 2 == 1)
	x = 0
	p2 = 1
	for _ in range(bits):
		(r, lb) = zip(*(divmod(a, 2) for a in red))
		add = sum(lb) % 2 == 1
		if add:
			red = list((a + b for (a, b) in zip(r, lb)))
			x += p2
		else:
			red = r
		p2 *= 2
	thr = p2 - x
	carry = list((v >= thr for v in vals))
	return (x, carry)
inp = stdin.readline
T = int(inp())
div = 12
pwr = 2 ** div
ans = []
for tx in range(T):
	N = int(inp())
	Ays = list((int(a) for a in inp().split()))
	carry = [False] * N
	x = 0
	pp = 1
	add = False
	while max(Ays) > 0:
		(Ays, lb) = zip(*(divmod(a + c, pwr) for (a, c) in zip(Ays, carry)))
		(mx, carry) = val_xor(lb, div)
		x += pp * mx
		pp *= pwr
	if sum(carry) % 2 == 1:
		ans.append(-1)
	else:
		ans.append(x)
print(*ans, sep='\n')


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)

def xor(l):
	ans = 0
	for i in l:
		ans ^= i
	return ans

def add(el, l):
	l1 = list(l)
	for i in range(len(l)):
		l1[i] += el
	return l1
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = max(l)
	m = len(bin(m)) - 1
	ans = 0
	pos = 0
	while True:
		_xor = xor(l)
		if _xor == 0:
			print(ans)
			break
		b = str(bin(_xor))[2:]
		if b[-pos - 1] == '1':
			element = 2 ** pos
			ans += element
			l = add(element, l)
		pos += 1
		if pos >= m - 1:
			print(-1)
			break


import math
for _ in range(int(input())):
	n = int(input())
	arr = [int(s) for s in input().split()]
	mx = max(arr)
	if mx == 0:
		ml = 1
	else:
		ml = math.ceil(math.log2(mx))
	p = 1
	r = 0
	bx = 0
	ai = set()
	for ii in range(n):
		ai.add(ii)
		bx = bx ^ arr[ii]
	bx = bin(bx)[::-1]
	con = bx.find('1')
	ad = 1
	conprev = 0
	while con < ml and con != -1:
		ad *= pow(2, con - conprev)
		bx = 0
		r += ad
		for i in ai:
			arr[i] += ad
			bx = bx ^ arr[i]
		bx = bin(bx)[::-1]
		conn = -1
		if len(bx) > conprev + 1:
			for j in range(conprev + 1, len(bx)):
				if bx[j] == '1':
					conn = j
					break
		(conprev, con) = (con, conn)
	if con == -1:
		print(r)
	else:
		print(-1)


import numpy as np
t = int(input())
while t:
	t = t - 1
	n = int(input())
	a = np.array(list(map(int, input().split())))
	cry = np.zeros(n, dtype=int)
	add = []
	for lmd in range(64):
		odd = np.sum((a + cry) % 2)
		if odd % 2:
			add.append(1)
			cry = a % 2 | cry % 2
			a = a // 2
		else:
			add.append(0)
			cry = a % 2 & cry % 2
			a = a // 2
	if sum(cry) > 0:
		print(-1)
	else:
		num = 0
		add.reverse()
		for x in add:
			num = num * 2 + x
		print(num)


def compute(A, X):
	S = 0
	for a in A:
		S ^= a + X
	return S

def naive(N, A):
	for x in range(10):
		S = compute(A, x)
		if not S:
			return x
	return -1

def main(N, A):
	X = 0
	for k in range(64):
		s = compute(A, X) >> k & 1
		if s == 1:
			X += 1 << k
	if compute(A, X):
		return -1
	return X
T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	A = [int(x) for x in input().strip().split()[:N]]
	print(main(N, A))


try:
	from debugger import debug
except ImportError:

	def debug(**kwargs):
		pass
	pass

def SolveCase():
	n = int(input())
	arr = list(map(int, input().split()))
	mask = 0
	for bit in range(63):
		xor = 0
		for x in arr:
			xor ^= x + mask
		if xor == 0:
			return mask
		if xor >> bit & 1:
			mask |= 1 << bit
	return -1
for _ in range(int(input())):
	print(SolveCase())