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.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Neighboring Bitwise XOR solution in C++
  4. Neighboring Bitwise XOR solution in Java
  5. Neighboring Bitwise XOR solution in Python
  6. 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.

See also  2654. Minimum Number of Operations to Make All Array Elements Equal to 1 LeetCode Solution

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

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.