Neighboring Bitwise XOR - Video Solutions
Neighboring Bitwise XOR | 2 Detailed Approaches | Dry Runs | Leetcode 2683 | codestorywithMIK
Neighboring Bitwise XOR - Video Solution
Watch 10 video solutions for Neighboring Bitwise XOR, a medium level problem involving Array, Bit Manipulation. This walkthrough by codestorywithMIK has 7,293 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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, thenderived[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.length1 <= n <= 105- The values in
derivedare either 0's or 1's
Approach Overview
Problem 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.
Complexity Analysis
| 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. |