 # XOR2 - Editorial

Author: jeevanjyot
Testers: mexomerf, rivalq
Editorialist: iceknight1093

TBD

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