A $0$ indexed binary array original of length n is transformed into a derived binary array derived of length n by computing the bitwise $ ext{XOR}$ of adjacent elements:

• For each index i such that $0 \leq$ i $< n - 1$, derived[i] $=$ original[i] $\oplus$ original[i + 1].

• For the last index n - 1, derived[n - 1] $=$ original[n - 1] $\oplus$ original[0].

Given the array derived, return true if there exists a valid binary array original that could have produced derived, or false otherwise.

Constraints:

• n $=$ derived.length

• $1 \leq$ n $\leq 10^5$

• derived[i] is either $0$ or $1$ for all valid indices i

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.