XOR2 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: jeevanjyot
Testers: mexomerf, rivalq
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You have an array A. In one move, you can pick an index i (with 1 \leq i \lt N), an integer X, and set A_i \to A_i \oplus X and A_{i+1} \to A_{i+1} \oplus X.

Determine whether all the elements of A can be made equal.

EXPLANATION:

The main observation behind solving this task is the fact that the bitwise XOR of the entire array doesn’t change after an operation is performed.

Proof

Let S = A_1 \oplus A_2 \oplus \ldots \oplus A_N.
Suppose we perform an operation on positions (i, i+1) with value X. The bitwise XOR of the new array is A_1 \oplus A_2 \oplus \ldots \oplus (A_i \oplus X) \oplus (A_{i+1}\oplus X) \oplus \ldots \oplus A_N.

This equals S \oplus X \oplus X = S.

Now, suppose we were able to make our final array such that A_i = y for every 1 \leq i \leq N (where y is some integer).
The bitwise XOR of this array is \underbrace{y\oplus y \oplus y \oplus \ldots \oplus y}_{N \text{ times}}.

  • If N is even, this is simply 0 because y\oplus y = 0.
    • So, if N is even, the bitwise XOR of the original array must be 0 for the answer to be YES.
  • If N is odd, this is y.
    • This gives us no further restrictions, since we can choose y to be the bitwise XOR of the whole array and the equation is satisfied.

In fact, this solves the problem!

  • If N is odd, the answer is always YES.
  • If N is even, the answer is YES if and only if the bitwise XOR of the whole array is 0.
Proof

Consider the case when N is odd. Let y be the bitwise XOR of the whole array.
Let’s make A_i equal to y for each i from 1 to N in order.

For each i from 1 to N-1:

  • Let X = A_i \oplus y. Perform the operation on (i, i+1) with this X.
    • Note that A_i changes to A_i \oplus X = A_i \oplus A_i \oplus y = y.
  • This allows us to make all of A_1, A_2, \ldots, A_{N-1} equal to y.
  • This automatically makes A_N equal to y.
    • This follows from the fact that the bitwise XOR of the whole array must be y; and the bitwise XOR of the first N-1 elements is 0 (since it’s an even number of copies of y).
    • So, the remaining element must be y.

The same construction works for the case when N is even and the bitwise XOR of the whole array is 0: just make the first N-1 elements 0, and the last element automatically becomes 0.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    xorsum = 0
    for x in a: xorsum ^= x
    if n%2 == 1 or xorsum == 0: print('Yes')
    else: print('No')
1 Like