Neighboring Bitwise XOR solution and explanation
Google
9 more videos on this problem
Neighboring Bitwise XOR | 2 Detailed Approaches | Dry Runs | Leetcode 2683 | codestorywithMIKcodestorywithMIK · 47:01 · 7K views
Neighboring Bitwise XOR - Leetcode 2683 - PythonNeetCodeIO · 12:10 · 6K views
Neighboring Bitwise XOR | Leetcode 2683Techdose · 5:49 · 3K views
2683. Neighboring Bitwise XOR (Leetcode Medium)Programming Live with Larry · 9:56 · 310 views
Daily Leetcode #1753: Jan 17, 2025 - 2683. Neighboring Bitwise XORProgramming Live with Larry · 15:33 · 279 views
2683. Neighboring Bitwise XOR | Leetcode Daily ChallengeEthos Typos · 9:08 · 143 views
2683. Neighboring Bitwise XOR LeetcodeNoob Coder · 15:16 · 117 views
LeetCode 2683 Neighboring Bitwise XOR | Bit Manipulation | Mastering XOR OperationsCode Harmony · 18:25 · 108 views
Neighboring Bitwise XOR | LEETCODE 2683 || #programming #dsa #algorithm #amazon#faang#dailypracticecodemintt · 19:33 · 78 views
2683. Neighboring Bitwise XOR | Leetcode | Weekly Contest 345 | Solution Code.Optimization · 3:43 · 53 views
The 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, 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.
Approach 1: Cycle Check via XOR Sum
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.
def is_valid(derived):
xor_sum = 0
for d in derived:
xor_sum ^= d
return xor_sum == 0public class Solution {
public boolean isValid(int[] derived) {
int xor_sum = 0;
for (int d : derived) {
xor_sum ^= d;
}
return xor_sum == 0;
}
}#include <vector>
bool isValid(std::vector<int>& derived) {
int xor_sum = 0;
for (int val : derived) {
xor_sum ^= val;
}
return xor_sum == 0;
}function isValid(derived) {
let xorSum = 0;
for (let d of derived) {
xorSum ^= d;
}
return xorSum === 0;
}#include <stdbool.h>
#include <stddef.h>
bool isValid(int* derived, size_t n) {
int xor_sum = 0;
for (size_t i = 0; i < n; i++) {
xor_sum ^= derived[i];
}
return xor_sum == 0;
}public class Solution {
public bool IsValid(int[] derived) {
int xorSum = 0;
foreach (var d in derived) {
xorSum ^= d;
}
return xorSum == 0;
}
}In Python, we iterate over the array and apply XOR summation across all elements to test cycle validity. This leads to a concise solution.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Reconstruct and Verify
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.
def try_reconstruction(derived, start):
n = len(derived)
original = [0] * n
original[0] = start
for i in range(1, n):
original[i] = derived[i-1] ^ original[i-1]
return (original[n-1] ^ derived[n-1]) == original[0]
def is_valid(derived):
return try_reconstruction(derived, 0) or try_reconstruction(derived, 1)public class Solution {
private boolean tryReconstruction(int[] derived, int start) {
int n = derived.length;
int[] original = new int[n];
original[0] = start;
for (int i = 1; i < n; i++) {
original[i] = derived[i-1] ^ original[i-1];
}
return (original[n-1] ^ derived[n-1]) == original[0];
}
public boolean isValid(int[] derived) {
return tryReconstruction(derived, 0) || tryReconstruction(derived, 1);
}
}#include <vector>
bool tryReconstruction(const std::vector<int>& derived, int start) {
std::vector<int> original(derived.size());
original[0] = start;
for (size_t i = 1; i < derived.size(); ++i) {
original[i] = derived[i-1] ^ original[i-1];
}
return (original.back() ^ derived.back()) == original[0];
}
bool isValid(std::vector<int>& derived) {
return tryReconstruction(derived, 0) || tryReconstruction(derived, 1);
}function tryReconstruction(derived, start) {
let n = derived.length;
let original = new Array(n).fill(0);
original[0] = start;
for (let i = 1; i < n; i++) {
original[i] = derived[i-1] ^ original[i-1];
}
return (original[n-1] ^ derived[n-1]) === original[0];
}
function isValid(derived) {
return tryReconstruction(derived, 0) || tryReconstruction(derived, 1);
}#include <stdbool.h>
#include <stdlib.h>
bool try_reconstruction(int* derived, size_t n, int start) {
int* original = (int*)malloc(n * sizeof(int));
original[0] = start;
for (size_t i = 1; i < n; i++) {
original[i] = derived[i-1] ^ original[i-1];
}
bool result = ((original[n-1] ^ derived[n-1]) == original[0]);
free(original);
return result;
}
bool isValid(int* derived, size_t n) {
return try_reconstruction(derived, n, 0) || try_reconstruction(derived, n, 1);
}public class Solution {
private bool TryReconstruction(int[] derived, int start) {
int n = derived.Length;
int[] original = new int[n];
original[0] = start;
for (int i = 1; i < n; i++) {
original[i] = derived[i-1] ^ original[i-1];
}
return (original[n-1] ^ derived[n-1]) == original[0];
}
public bool IsValid(int[] derived) {
return TryReconstruction(derived, 0) || TryReconstruction(derived, 1);
}
}Leveraging the flexibility of Python, we assess both possibilities of the starting value (0 and 1), performing separate reconstructions to derive a correct course of action.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Bit Manipulation
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)$.
function doesValidArrayExist(derived: number[]): boolean {
return derived.reduce((acc, x) => acc ^ x) === 0;
}func doesValidArrayExist(derived []int) bool {
s := 0
for _, x := range derived {
s ^= x
}
return s == 0
}impl Solution {
pub fn does_valid_array_exist(derived: Vec<i32>) -> bool {
derived.iter().fold(0, |acc, &x| acc ^ x) == 0
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Cycle Check via XOR Sum | Time Complexity: O(n) Space Complexity: O(1) |
| Reconstruct and Verify | Time Complexity: O(n) Space Complexity: O(n) |
| Bit Manipulation | – |
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. |
Frequently asked questions
Is Neighboring Bitwise XOR easy or hard?
Neighboring Bitwise XOR is classified as Medium difficulty. The implementation is simple, but recognizing that all original elements cancel out in the XOR cycle requires understanding of XOR algebra and circular array relationships.
Neighboring Bitwise XOR Python/Java solution
In Python or Java, the optimal implementation iterates through the array and XORs every value into a variable. After the loop, return true if the XOR equals 0. The implementation is typically fewer than 10 lines and runs in O(n) time.
How to solve Neighboring Bitwise XOR in O(n)?
Iterate through the derived array and maintain a running XOR of all elements. Because every original value appears twice in the circular XOR equations, they cancel out. If the final XOR of the derived array equals 0, a valid original array exists; otherwise it does not.
What is the best approach for Neighboring Bitwise XOR?
The most efficient approach is the XOR cycle check. XOR all values in the derived array and verify that the result equals 0. If the total XOR is zero, a valid original binary array exists. This solution runs in O(n) time with O(1) space.
Is Neighboring Bitwise XOR asked at Google/Amazon/Meta?
Bit manipulation and XOR reasoning problems similar to Neighboring Bitwise XOR frequently appear in interviews at companies like Amazon, Google, and Meta. The question tests understanding of XOR properties and circular array constraints.
What data structure is used in Neighboring Bitwise XOR?
The problem mainly relies on arrays and bit manipulation. The optimal solution does not require additional data structures; it only computes a cumulative XOR while iterating through the array.
What is the time complexity of Neighboring Bitwise XOR?
The optimal algorithm runs in O(n) time because it performs a single pass through the derived array to compute the cumulative XOR. Space complexity is O(1) since only a single variable is needed to track the XOR sum.