Xor Equation XOREQN Solution

Xor Equation XOREQN Solution Codechef

by

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

Leave a Comment

15 − 3 =