# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* jeevanjyot

*mexomerf, rivalq*

**Testers:***iceknight1093*

**Editorialist:**# 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`

.

- So, if N is even, the bitwise XOR of the original array
- 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')
```