Problem

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, then derived[i] = original[i] ⊕ original[0].
  • Otherwise, derived[i] = original[i] ⊕ original[i + 1].

Given an array derived, your task is to 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

Examples

Example 1:

1
2
3
4
5
6

Input: derived = [1,1,0]
Output: true
Explanation: A valid original array that gives derived is [0,1,0].
derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1 
derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1
derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0

Example 2:

1
2
3
4
5

Input: derived = [1,1]
Output: true
Explanation: A valid original array that gives derived is [0,1].
derived[0] = original[0] ⊕ original[1] = 1
derived[1] = original[1] ⊕ original[0] = 1

Example 3:

1
2
3

Input: derived = [1,0]
Output: false
Explanation: There is no valid original array that gives derived.

Constraints:

  • n == derived.length
  • 1 <= n <= 10^5
  • The values in derived are either 0 ’s or 1 ’s

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Xor of whole of derived should be 0

Lets take original array be A[0], A[1], ... A[n-1]. Then the derived array will be:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

[
	A[0] ^ A[1],
	A[1] ^ A[2],
	A[2] ^ A[3],
	.
	.
	.
	A[n - 2] ^ A[n - 1],
	A[n - 1] ^ A[0]
 ]

Now, we know that:

1
2

x ^ x = 0
x ^ 0 = x

So, if we perform XOR between the elements of derived, they should cancel out:

So, if xoring the derived values results in 0, we can derive this array from original array.

Code

1
2
3
4
5
6
7
8
9

public class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        int xor = 0;
        for (int num : derived) {
            xor ^= num;
        }
        return xor == 0;
    }
}
1
2
3
4
5
6

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        xor: int = 0
        for num in derived:
            xor ^= num
        return xor == 0

Complexity

  • ⏰ Time complexity: O(n) - We iterate through the derived array once.
  • 🧺 Space complexity: O(1), We use a constant amount of extra space (variable to store XOR value).

Method 2 - Sum should be even

If the xor values of derived is 0, and derived is a binary array, then:

  1. Each XOR operation will essentially contribute either 0 or 1 to the derived array.
  2. For the XOR of all derived elements to be zero, they must pair off and cancel each other out (since x ⊕ x = 0).

When dealing with binary elements:

  • An even count of 1s ensures they can cancel each other out in pairs (every 1 in the XOR sequence finds another 1 to pair with and cancel out).
  • Therefore, for the derived array to be valid (derived from a valid original array), the sum of 1s (i.e., the sum of its elements) must be even.

Code

1
2
3
4
5
6
7
8
9

public class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        int sum = 0;
        for (int num : derived) {
            sum += num;
        }
        return sum % 2 == 0;
    }
}
1
2
3

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        return sum(derived) % 2 == 0