Watch 10 video solutions for Neighboring Bitwise XOR, a medium level problem involving Array, Bit Manipulation. This walkthrough by codestorywithMIK has 7,102 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |