LeetCode 2683. Neighboring Bitwise XOR Solution in Java, C++, Python & More | Explanation + Code

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₀ = a₀ \oplus a₁ \ b₁ = a₁ \oplus a₂ \ … \ b_n-1 = a_n-1 \oplus a₀

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

b₀ \oplus b₁ \oplus … \oplus b_n-1 = (a₀ \oplus a₁) \oplus (a₁ \oplus a₂) \oplus … \oplus (a_n-1 \oplus a₀) = 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).

PythonJavaC++GoTypeScriptRustJavaScriptC#

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

class Solution { public boolean doesValidArrayExist(int[] derived) { int s = 0; for (int x : derived) { s ^= x; } return s == 0; } }(code-box)

class Solution { public: bool doesValidArrayExist(vector<int>& derived) { int s = 0; for (int x : derived) { s ^= x; } return s == 0; } };(code-box)

func doesValidArrayExist(derived []int) bool { s := 0 for _, x := range derived { s ^= x } return s == 0 }(code-box)

function doesValidArrayExist(derived: number[]): boolean { return derived.reduce((acc, x) => acc ^ x) === 0; }(code-box)

impl Solution { pub fn does_valid_array_exist(derived: Vec<i32>) -> bool { derived.iter().fold(0, |acc, &x| acc ^ x) == 0 } }(code-box)

/** * @param {number[]} derived * @return {boolean} */ var doesValidArrayExist = function (derived) { return derived.reduce((acc, x) => acc ^ x) === 0; };(code-box)

public class Solution { public bool DoesValidArrayExist(int[] derived) { return derived.Aggregate(0, (acc, x) => acc ^ x) == 0; } }(code-box)