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.
Subtasks
Subtask 1 (20 points):
- 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.
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
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;
}
November Long Challenge 2021 Solution
- Which Fuel is Cheaper CHEAPFUEL Solution
- Convex Hulk CONHULK Solution
- Functional Array FUNARR Solution
- Flip or Compress FLIPCOMP Solution
- Maximise the bridges MAXBRIDGE Solution
- Wildcard Replacement WLDRPL Solution
- Xor Equation XOREQN Solution
- Hill Sequence HILLSEQ Solution
- Weird Palindrome Making MAKEPAL Solution
- Equal Coins EQUALCOIN Solution Codechef