Neighboring Bitwise XOR

Med

#2432Time: 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.

Patterns

Bit Manipulation

Data structures

Array

Prompt

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] &oplus; original[1] = 0 &oplus; 1 = 1 
derived[1] = original[1] &oplus; original[2] = 1 &oplus; 0 = 1
derived[2] = original[2] &oplus; original[0] = 0 &oplus; 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] &oplus; original[1] = 1
derived[1] = original[1] &oplus; 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 <= 10⁵
The values in derived are either 0's or 1's

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public boolean doesValidArrayExist(int[] derived) {3        // Helper function to check a given starting value for original[0]4        if (check(derived, 0)) {5            return true;6        }7        // If starting with 0 fails, try starting with 18        if (check(derived, 1)) {9            return true;10        }11        return false;12    }13 14    private boolean check(int[] derived, int firstElement) {15        int n = derived.length;16        int[] original = new int[n];17        original[0] = firstElement;18 19        // Construct the rest of the original array20        for (int i = 0; i < n - 1; i++) {21            original[i + 1] = original[i] ^ derived[i];22        }23 24        // Check if the last element relationship holds25        // derived[n - 1] = original[n - 1] ^ original[0]26        return (original[n - 1] ^ original[0]) == derived[n - 1];27    }28}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

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

Complexity

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.

Trade-offs

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.

Solutions

Solution

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

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

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem