Skip to content

2683. Neighboring Bitwise XOR

Description

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

 

Example 1:

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:

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:

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

 

Constraints:

  • n == derived.length
  • 1 <= n <= 105
  • The values in derived are either 0's or 1's

Solutions

Solution 1: Bit Manipulation

Let's assume the original binary array is \(a\), and the derived array is \(b\). Then, we have:

\[ b_0 = a_0 \oplus a_1 \\ b_1 = a_1 \oplus a_2 \\ \cdots \\ b_{n-1} = a_{n-1} \oplus a_0 \]

Since the XOR operation is commutative and associative, we get:

\[ b_0 \oplus b_1 \oplus \cdots \oplus b_{n-1} = (a_0 \oplus a_1) \oplus (a_1 \oplus a_2) \oplus \cdots \oplus (a_{n-1} \oplus a_0) = 0 \]

Therefore, as long as the XOR sum of all elements in the derived array is \(0\), there must exist an original binary array that meets the requirements.

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

1
2
3
class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        return reduce(xor, derived) == 0

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        int s = 0;
        for (int x : derived) {
            s ^= x;
        }
        return s == 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        int s = 0;
        for (int x : derived) {
            s ^= x;
        }
        return s == 0;
    }
};

1
2
3
4
5
6
7
func doesValidArrayExist(derived []int) bool {
    s := 0
    for _, x := range derived {
        s ^= x
    }
    return s == 0
}

1
2
3
function doesValidArrayExist(derived: number[]): boolean {
    return derived.reduce((acc, x) => acc ^ x) === 0;
}

Comments