Xor Equation XOREQN Solution

Xor Equation XOREQN Solution Codechef

by

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

Codechef Long Challenges Solution

October Long Challenge 2021 Solution

September Long Challenge 2021 Solution

Leave a Comment