Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 summary: 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
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Bit Manipulation
[1,1,0]
[1,1]
[1,0]
bitwise-or-of-adjacent-elements)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2683: Neighboring Bitwise XOR
class Solution {
public boolean doesValidArrayExist(int[] derived) {
int s = 0;
for (int x : derived) {
s ^= x;
}
return s == 0;
}
}
// Accepted solution for LeetCode #2683: Neighboring Bitwise XOR
func doesValidArrayExist(derived []int) bool {
s := 0
for _, x := range derived {
s ^= x
}
return s == 0
}
# Accepted solution for LeetCode #2683: Neighboring Bitwise XOR
class Solution:
def doesValidArrayExist(self, derived: List[int]) -> bool:
return reduce(xor, derived) == 0
// Accepted solution for LeetCode #2683: Neighboring Bitwise XOR
impl Solution {
pub fn does_valid_array_exist(derived: Vec<i32>) -> bool {
derived.iter().fold(0, |acc, &x| acc ^ x) == 0
}
}
// Accepted solution for LeetCode #2683: Neighboring Bitwise XOR
function doesValidArrayExist(derived: number[]): boolean {
return derived.reduce((acc, x) => acc ^ x) === 0;
}
Use this to step through a reusable interview workflow for this problem.
Sort the array in O(n log n), then scan for the missing or unique element by comparing adjacent pairs. Sorting requires O(n) auxiliary space (or O(1) with in-place sort but O(n log n) time remains). The sort step dominates.
Bitwise operations (AND, OR, XOR, shifts) are O(1) per operation on fixed-width integers. A single pass through the input with bit operations gives O(n) time. The key insight: XOR of a number with itself is 0, which eliminates duplicates without extra space.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.