⚡Flashcard Drill➔
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

  1. Fixing original[0] forces every other value: original[i + 1] = original[i] ^ derived[i].
  2. Chaining the equations all the way around leaves one consistency condition on the wrap-around pair (n - 1, 0).
  3. XOR-ing all n equations together makes the original terms cancel in pairs, leaving the XOR of derived on one side and zero on the other.
  4. So a valid original exists exactly when the XOR of all of derived is 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 derived with original: the parity argument applies to derived, whose XOR must be even.
  • Assuming n must be even: the condition holds for both parities of n.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Bit Manipulation Problems