NeetCode #869LC-2683MediumBit Manipulation
← Back to All Problems#869 · #2683 · Neighboring Bitwise XOR(相邻值的按位异或)
📌 Problem Statement & Constraints
A binary array
original of length n derives an array derived where derived[i] = original[i] XOR original[(i + 1) % n]. Given derived, return whether at least one valid original exists. Constraints: 1 <= n <= 10^5, and each derived[i] is 0 or 1.💡 Core Algorithmic Approaches
- Fixing
original[0]forces every other value:original[i + 1] = original[i] ^ derived[i]. - Chaining the equations all the way around leaves one consistency condition on the wrap-around pair
(n - 1, 0). - XOR-ing all
nequations together makes theoriginalterms cancel in pairs, leaving the XOR ofderivedon one side and zero on the other. - So a valid
originalexists exactly when the XOR of all ofderivedis 0.
💻 Benchmark Python3 Implementation
class Solution:
def doesValidArrayExist(self, derived: List[int]) -> bool:
res = 0
for x in derived:
res ^= x # the cycle must close consistently
return res == 0⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): a single pass.
💾 Space Complexity
O(1): one accumulator.
⚠️ Interview Pitfalls & Follow-ups
- Simulating both starting values of
original[0]: it works but is twice the work; the total-XOR test is the shortcut. - Ignoring the cyclic pair: the condition
derived[n - 1] = original[n - 1] ^ original[0]is what forces the total XOR to vanish. - Confusing
derivedwithoriginal: the parity argument applies toderived, whose XOR must be even. - Assuming
nmust be even: the condition holds for both parities ofn.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.