2683. Neighboring Bitwise XOR LeetCode Solution

In this guide, you will get 2683. Neighboring Bitwise XOR LeetCode Solution with the best time and space complexity. The solution to Neighboring Bitwise XOR problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Neighboring Bitwise XOR solution in C++
Neighboring Bitwise XOR solution in Java
Neighboring Bitwise XOR solution in Python
Additional Resources

2683. Neighboring Bitwise XOR LeetCode Solution image

Problem Statement of 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, 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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

2683. Neighboring Bitwise XOR LeetCode Solution in C++

class Solution {
 public:
  bool doesValidArrayExist(vector<int>& derived) {
    //      original = [O[0], O[1], ..., O[n - 1]]
    //       derived = [O[0]^O[1], O[1]^O[2], ..., O[n - 1]^O[0]]
    // XOR(derivedd) = 0
    return accumulate(derived.begin(), derived.end(), 0, bit_xor<>()) == 0;
  }
};
/* code provided by PROGIEZ */

2683. Neighboring Bitwise XOR LeetCode Solution in Java

class Solution {
  public boolean doesValidArrayExist(int[] derived) {
    //      original = [O[0], O[1], ..., O[n - 1]]
    //       derived = [O[0]^O[1], O[1]^O[2], ..., O[n - 1]^O[0]]
    // XOR(derivedd) = 0
    return Arrays.stream(derived).reduce((a, b) -> a ^ b).getAsInt() == 0;
  }
}
// code provided by PROGIEZ

2683. Neighboring Bitwise XOR LeetCode Solution in Python

class Solution:
  def doesValidArrayExist(self, derived: list[int]) -> bool:
    return functools.reduce(operator.xor, derived) == 0
 # code by PROGIEZ