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]:
i = n - 1, then derived[i] = original[i] ⊕ original[0].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.
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.length1 <= n <= 105derived are either 0's or 1'sProblem Overview: You are given a binary array derived where derived[i] = original[i] XOR original[(i+1) % n]. The task is to determine whether there exists a binary array original that could produce this derived array. The challenge comes from the circular dependency between the first and last elements.
Approach 1: Reconstruct and Verify (O(n) time, O(n) space)
Start by guessing the first value of original. Since the array is binary, the first element can only be 0 or 1. Once the first value is fixed, every other element is determined by the equation original[i+1] = original[i] XOR derived[i]. Iterate through the array and reconstruct the entire original sequence. After reconstruction, verify the circular condition: derived[n-1] == (original[n-1] XOR original[0]). If this holds for either starting guess, a valid array exists. This approach explicitly simulates the relationship defined in the problem and is helpful for understanding how arrays interact with bit manipulation operations.
Approach 2: Cycle Check via XOR Sum (O(n) time, O(1) space)
The XOR relationships form a cycle across the array. Expanding the definition of derived gives a chain of equations: derived[0] = o0 XOR o1, derived[1] = o1 XOR o2, and so on, until derived[n-1] = o(n-1) XOR o0. XOR all equations together. Every original element appears exactly twice in the XOR expression, and x XOR x = 0, so they cancel out. The remaining condition is derived[0] XOR derived[1] XOR ... XOR derived[n-1] = 0. If the total XOR of the derived array equals zero, a valid original array must exist; otherwise, it is impossible. This observation removes the need to reconstruct the array entirely and turns the problem into a single pass using XOR accumulation.
This approach relies on properties of bit manipulation and XOR cancellation. You simply iterate through the array, maintain a running XOR, and check whether the final value equals zero. Because it uses only a single variable and one traversal, the space complexity is constant.
Recommended for interviews: The XOR cycle check is the expected solution. It demonstrates understanding of XOR algebra and circular constraints while achieving O(n) time and O(1) space. Reconstructing the array is a good reasoning step and shows you understand the equation, but recognizing the XOR cancellation pattern is the insight interviewers usually look for.
If there's a valid original array for a cycle, the sum of XOR results over the entire cycle must equal 0. Thus, you need to ensure the whole XOR sum of derived results in a consistent cycle.
Explanation: If you think about the cycle formed by the derived array indices, the conditions would imply that the XOR of all the derived elements should equal 0 in a valid binary sequence as every XOR pairs with its adjacent at least once in a valid set.
The solution iterates over the derived array and calculates the XOR sum of all the values. If the result is 0, it indicates a valid cycle exists for the binary array.
Time Complexity: O(n), where n is the number of elements in the derived array. We iterate through the array once.
Space Complexity: O(1), as we are only using a constant amount of extra space.
Attempt to reconstruct the original array by assuming initial possibilities and verify closure of cycle:
We shall try reconstructing the binary array by assuming the possible initial values (either 0 or 1) and iterating over each index to generate the subsequent value, checking if at the end, original[n] matches original[0] as intended.
We attempt possible reconstructions of the binary sequence starting with either 0 or 1. Using a helper function, we propagate potential values through original, verifying the closure for cycle integrity.
Time Complexity: O(n), as two full passes of the derived array may be performed in the worst case.
Space Complexity: O(n), due to temporary storage needed for reconstruction.
Let's assume the original binary array is a, and the derived array is b. Then, we have:
$
b_0 = a_0 \oplus a_1 \
b_1 = a_1 \oplus a_2 \
cdots \
b_{n-1} = a_{n-1} \oplus a_0
Since the XOR operation is commutative and associative, we get:
b_0 \oplus b_1 \oplus cdots \oplus b_{n-1} = (a_0 \oplus a_1) \oplus (a_1 \oplus a_2) \oplus cdots \oplus (a_{n-1} \oplus a_0) = 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)$.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| Cycle Check via XOR Sum | Time Complexity: O(n), where n is the number of elements in the Space Complexity: O(1), as we are only using a constant amount of extra space. |
| Reconstruct and Verify | Time Complexity: O(n), as two full passes of the derived array may be performed in the worst case. Space Complexity: O(n), due to temporary storage needed for reconstruction. |
| Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reconstruct and Verify | O(n) | O(n) | Useful for understanding the relationship between original and derived arrays or when explicitly reconstructing the sequence. |
| Cycle Check via XOR Sum | O(n) | O(1) | Best general solution. Uses XOR cancellation to validate the circular constraint without reconstruction. |
Neighboring Bitwise XOR | 2 Detailed Approaches | Dry Runs | Leetcode 2683 | codestorywithMIK • codestorywithMIK • 7,102 views views
Watch 9 more video solutions →Practice Neighboring Bitwise XOR with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor