# Xor Equation XOREQN Solution Codechef

## Xor Equation XOREQN Solution

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(A1+x)⊕(A2+x)⊕⋯⊕(AN+x)=0 where ⊕ 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 A1,A2…AN.

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≤105
• 1≤N≤106
• 0≤Ai≤1018
• The value of N is guaranteed to be odd.
• Sum of N over all test cases is less than or equal to 106.

• 1≤T≤103
• 1≤N≤103
• 0≤Ai≤103
• The value of N is guaranteed to be odd.
• Sum of N over all test cases is less than or equal to 103.

• 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

Test case 1:

We have to find minimum non-negative integer x such that (2+x)⊕(4+x)⊕(5+x)=0 Let f(x)=(2+x)⊕(4+x)⊕(5+x).

• For x=0, we have f(0)=(2+0)⊕(4+0)⊕(5+0)=2⊕4⊕5=3
• For x=1, we have f(1)=(2+1)⊕(4+1)⊕(5+1)=3⊕5⊕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)⊕(0+x)⊕(0+x)=0 i.e. x⊕x⊕x=0. But since 0⊕0⊕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)⊕(1+x)⊕(1+x)=0 But a⊕a=0 and 0⊕a=a for any non-negative integer a. It follows that (1+x)⊕(1+x)⊕(1+x)=0⊕(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 xx that satisfies the given equation.

Test case 4:

• We have to find minimum non-negative integer xx such that(1+x)⊕(1+x)⊕(2+x)=0 It follows that (1+x)⊕(1+x)⊕(2+x)=0⊕(2+x)=2+x
• This implies that xx 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.

### SOLUTION

Program Python: Xor Equation XOREQN Solution in Python

``````for _ in range(int(input())):
n = int(input())
lst = list(map(int,input().split()))
string = ''
shft = cnt = 0
mx = -20
ans = 0
while mx:
mx = 0
for x in lst:
cnt += 1 if (x >> shft) & 1 else 0
mx = max(mx,x >> shft)
if (cnt & 1 and (n - cnt) & 1) or shft > 21:
print(-1)
break
if cnt & 1:
for x in range(n):
lst[x] += 1 << shft
ans += 1 << shft
shft += 1
cnt = 0
else:
print(ans)``````

Program C++: Xor Equation XOREQN Solution in C++

``````#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
#define fast                          \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);                    \
cout.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define Sort(v) sort(all(v))
#define pb push_back
#define mkp make_pair
#define ff first
#define ss second
#define endl cout << "\n"
#define rep(i, p, q) for (int i = p; i < q; i++)
#define repre(i, p, q) for (int i = p; i >= q; i--)
#define lcm(a, b) ((a * b) / __gcd(a, b))
#define inp(v, n)  \
rep(i, 0, n)   \
cin >> \
v[i];
#define test  \
int t;    \
cin >> t; \
while (t--)
const int MOD = 1000000007;
int main()
{
fast;
test
{
ll n, i, x = 1, c = 0, s = 0, val = 0;
cin >> n;
vl a(n);
inp(a, n);
rep(i, 0, 64)
{
c=0;
rep(j, 0, n)
{
if (x & a[j])
c++;
}
if (c & 1)
s += x;
if (c & 1)
{
//cout<<i<<"---->\n";
rep(j, 0, n)
{
a[j] += x;
//cout<<a[j]<<" ";
}
}
x <<= 1;
}
rep(i, 0, n)
{
val ^= a[i];
}
if (val == 0 && (c%2==0))
cout << s << "\n";
else
cout << "-1\n";
}
return 0;
}``````