Xor Equation solution codechef

Xor Equation solution codechef

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.

Xor Equation solution codechef

  • 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,A2ANA1,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.

Xor Equation solution codechef

  • 1T1051≤T≤105
  • 1N1061≤N≤106
  • 0Ai10180≤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

Xor Equation solution codechef

  • 1T1031≤T≤103
  • 1N1031≤N≤103
  • 0Ai1030≤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

Xor Equation solution codechef

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)=0

Let f(x)=(2+x)(4+x)(5+x)f(x)=(2+x)⊕(4+x)⊕(5+x).

  • For x=0x=0, we have
    f(0)=(2+0)(4+0)(5+0)=245=3f(0)=(2+0)⊕(4+0)⊕(5+0)=2⊕4⊕5=3
  • For x=1x=1, we have
    f(1)=(2+1)(4+1)(5+1)=356=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)=0

i.e. xxx=0x⊕x⊕x=0. But since 000=00⊕0⊕0=0, it follows that x=0x=0 is the minimum non-negative integer that satisfies the given equation.

Xor Equation solution codechef

We have to find minimum non-negative integer xx such that

(1+x)(1+x)(1+x)=0(1+x)⊕(1+x)⊕(1+x)=0

But aa=0a⊕a=0 and 0a=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)=0

It 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.

Leave a Comment