Neighboring Bitwise XOR
A 0-indexed array derived with length n is derived by computing the bitwise XOR (ā) of adjacent values in a binary array original of length n.
Specifically, for each index i in the range [0, n - 1]:
- If
i = n - 1, thenderived[i] = original[i] ā original[0]. - Otherwise,
derived[i] = original[i] ā original[i + 1].
Given an array derived, determine whether there exists a valid binary array original that could have formed derived.
Return true if such an array exists or false otherwise.
A binary array is an array containing only 0's and 1's.
Example 1
Input
derived = [1,1,0]Output
trueA valid original array that gives derived is [0, 1, 0], because each adjacent circular XOR produces [1, 1, 0].
Example 2
Input
derived = [1,1]Output
trueA valid original array that gives derived is [0, 1], because both circular adjacent XOR computations equal 1.
Constraints
- n == derived.length
- 1 <= n <= 10^5
- The values in
derivedare either 0's or 1's