Page Contents
Xor Equation XOREQN Solution
You are given an array AA of NN non-negative integers, where NN is odd. Find the minimum non-negative integer xx that satisfies the equation(A1+x)⊕(A2+x)⊕⋯⊕(AN+x)=0(A1+x)⊕(A2+x)⊕⋯⊕(AN+x)=0
where ⊕⊕ denotes the bitwise XOR operation. If no such xx exists, print −1−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 TT, the number of test cases. The description of TT test cases follows.
- The first line of each test case contains a single integer NN, denoting the size of the array AA.
- The second line of each test case contains NN space-separated non-negative integers A1,A2…ANA1,A2…AN.
Output Format
For each test case, print a single line containing one integer. If there does not exist any non-negative integer xx that satisfies the given equation, print −1−1. Otherwise, print the minimum value of xx that satisfies the given equation.
Constraints
- 1≤T≤1051≤T≤105
- 1≤N≤1061≤N≤106
- 0≤Ai≤10180≤Ai≤1018
- The value of NN is guaranteed to be odd.
- Sum of NN over all test cases is less than or equal to 106106.
Subtasks
Subtask 1 (20 points):
- 1≤T≤1031≤T≤103
- 1≤N≤1031≤N≤103
- 0≤Ai≤1030≤Ai≤103
- The value of NN is guaranteed to be odd.
- Sum of NN over all test cases is less than or equal to 103103.
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 xx such that(2+x)⊕(4+x)⊕(5+x)=0(2+x)⊕(4+x)⊕(5+x)=0Let f(x)=(2+x)⊕(4+x)⊕(5+x)f(x)=(2+x)⊕(4+x)⊕(5+x).
- For x=0x=0, we havef(0)=(2+0)⊕(4+0)⊕(5+0)=2⊕4⊕5=3f(0)=(2+0)⊕(4+0)⊕(5+0)=2⊕4⊕5=3
- For x=1x=1, we havef(1)=(2+1)⊕(4+1)⊕(5+1)=3⊕5⊕6=0f(1)=(2+1)⊕(4+1)⊕(5+1)=3⊕5⊕6=0
Therefore, x=1x=1 is the minimum non-negative integer that satisfies the given equation.
Test case 2:
We have to find minimum non-negative integer xx such that(0+x)⊕(0+x)⊕(0+x)=0(0+x)⊕(0+x)⊕(0+x)=0i.e. x⊕x⊕x=0x⊕x⊕x=0. But since 0⊕0⊕0=00⊕0⊕0=0, it follows that x=0x=0 is the minimum non-negative integer that satisfies the given equation.
Test case 3:
We have to find minimum non-negative integer xx such that(1+x)⊕(1+x)⊕(1+x)=0(1+x)⊕(1+x)⊕(1+x)=0But a⊕a=0a⊕a=0 and 0⊕a=a0⊕a=a for any non-negative integer aa. It follows that(1+x)⊕(1+x)⊕(1+x)=0⊕(1+x)=1+x(1+x)⊕(1+x)⊕(1+x)=0⊕(1+x)=1+x
This implies that xx satisfies the given equation if and only if it satisfies 1+x=01+x=0 if and only if x=−1x=−1. But −1−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(1+x)⊕(1+x)⊕(2+x)=0It follows that(1+x)⊕(1+x)⊕(2+x)=0⊕(2+x)=2+x(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=02+x=0, which can only happen if x=−2x=−2. But −2−2 is a negative integer and therefore, there does not exist any non-negative xx that satisfies the given equation, hence we output −1−1.
Xor Equation XOREQN Solution is updated. Click Below
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
Codechef Long Challenges Solution
October Long Challenge 2021 Solution
- Longest AND Subarray
- MEX-OR
- Digit Removal
- Yet another MEX problem
- Characteristic Polynomial Verification
- Chef at the Olympics
- Which Mixture
- Three Boxes
September Long Challenge 2021 Solution
- Airline Restrictions
- Travel Pass
- Shuffling Parities
- XOR Equal
- 2-D Point Meeting
- Minimize Digit Sum
- Minimum Digit Sum 2
- Treasure Hunt
- Covaxin vs Covishield