# Neighboring Bitwise XOR
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/neighboring-bitwise-xor)
Canonical: https://scaleengineer.com/dsa/problems/neighboring-bitwise-xor
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
---
## 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**

**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**

# Approaches
## Simulation by Fixing `original[0]`
This approach is based on the observation that the entire `original` array is determined if we know the value of its first element, `original[0]`. Since `original` is a binary array, `original[0]` can only be `0` or `1`. We can try both possibilities and check if either leads to a valid solution.
**Time:** O(n). We iterate through the `derived` array to construct the `original` array. This is done at most twice, resulting in a linear time complexity. · **Space:** O(n). We allocate an auxiliary array `original` of size `n` to store the constructed binary array.
**Pros:** It's a direct simulation of the problem statement, making it intuitive to understand.; It correctly solves the problem by exhaustively checking the only two possible scenarios.
**Cons:** Uses O(n) extra space to store the candidate `original` array, which can be inefficient for large inputs.; May require two passes over the data in the worst case.
### Explanation
This approach directly simulates the process of constructing the `original` array. The key insight is that if we fix the value of `original[0]`, all other elements `original[i]` are uniquely determined by the recurrence relation `original[i+1] = original[i] ^ derived[i]`. Since `original[0]` must be either 0 or 1, we have only two cases to check.

We can write a helper function that takes a potential starting value for `original[0]`, constructs the full `original` array, and then checks if this constructed array satisfies the final, wrap-around condition: `derived[n-1] == original[n-1] ^ original[0]`. If the check passes for either starting value (0 or 1), we have found a valid solution.

```java
class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        // Helper function to check a given starting value for original[0]
        if (check(derived, 0)) {
            return true;
        }
        // If starting with 0 fails, try starting with 1
        if (check(derived, 1)) {
            return true;
        }
        return false;
    }

    private boolean check(int[] derived, int firstElement) {
        int n = derived.length;
        int[] original = new int[n];
        original[0] = firstElement;

        // Construct the rest of the original array
        for (int i = 0; i < n - 1; i++) {
            original[i + 1] = original[i] ^ derived[i];
        }

        // Check if the last element relationship holds
        // derived[n - 1] = original[n - 1] ^ original[0]
        return (original[n - 1] ^ original[0]) == derived[n - 1];
    }
}
```
### Algorithm
- **Try `original[0] = 0`**:
  - Create a candidate `original` array of size `n`.
  - Set `original[0] = 0`.
  - Calculate the remaining elements `original[1], ..., original[n-1]` using the recurrence `original[i] = original[i-1] ^ derived[i-1]`.
  - Check if `derived[n-1] == original[n-1] ^ original[0]`. If true, return `true`.
- **Try `original[0] = 1`**:
  - If the first try failed, repeat the process with `original[0] = 1`.
  - If the final check is successful, return `true`.
- **No Solution**:
  - If both tries fail, return `false`.

## Bitwise XOR Sum Property
This approach uses a mathematical property of the bitwise XOR operation to solve the problem in a single pass with constant extra space. By XORing all the given equations, we find that a solution exists if and only if the XOR sum of all elements in the `derived` array is 0.
**Time:** O(n). We iterate through the `derived` array exactly once to compute the XOR sum. · **Space:** O(1). We only use a single integer variable to store the running XOR sum, which is constant extra space.
**Pros:** Highly efficient, with O(n) time and O(1) space complexity.; Elegant and concise solution.; Requires only a single pass over the input data.
**Cons:** The underlying mathematical insight might not be immediately obvious without analyzing the XOR properties.
### Explanation
A more efficient solution comes from a mathematical insight into the properties of the XOR operation. Let's analyze the system of equations given in the problem description:
`derived[0] = original[0] ^ original[1]`
`derived[1] = original[1] ^ original[2]`
...
`derived[n-1] = original[n-1] ^ original[0]`

If we take the bitwise XOR of all `n` equations, the left side becomes the XOR sum of the `derived` array. The right side becomes `(original[0] ^ original[1]) ^ (original[1] ^ original[2]) ^ ... ^ (original[n-1] ^ original[0])`. Due to the associative and commutative properties of XOR, we can reorder the terms. Each `original[i]` appears exactly twice. Since `x ^ x = 0`, the XOR sum of the right side is 0.

This leads to a simple condition: `derived[0] ^ derived[1] ^ ... ^ derived[n-1] = 0`. This condition is not only necessary but also sufficient. If the XOR sum of `derived` is 0, a valid `original` array can always be constructed. Therefore, we just need to compute the XOR sum of the `derived` array and check if it's zero.

```java
class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        int xorSum = 0;
        for (int x : derived) {
            xorSum ^= x;
        }
        return xorSum == 0;
    }
}
```
### Algorithm
- Initialize a variable, `xorSum`, to 0.
- Iterate through each element `d` in the `derived` array.
- In each iteration, update `xorSum` by XORing it with the current element: `xorSum = xorSum ^ d`.
- After the loop, if `xorSum` is 0, return `true`.
- Otherwise, return `false`.

# Solutions
### Java

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

```

### CPP

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

```

### Python

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

```