Neighboring Bitwise XOR

medium array bit manipulation xor parity

Problem

A binary array original of length n produces derived by XOR-ing adjacent values cyclically: derived[i] = original[i] ⊕ original[i+1] for i < n−1, and derived[n−1] = original[n−1] ⊕ original[0]. Given derived, decide whether any valid binary original could have formed it. Return true if one exists, otherwise false.

Inputderived = [1, 1, 0]

Outputtrue

original = [0, 1, 0] works: 0⊕1=1, 1⊕0=1, 0⊕0=0. The XOR of all derived values is 1⊕1⊕0 = 0, so a valid original exists.

derived (comma-separated 0/1)

def doesValidArrayExist(derived):
    # Each original[i] is used in exactly two derived terms,
    # so XOR-ing all derived values cancels every original[i].
    x = 0
    for v in derived:
        x ^= v               # fold the next derived bit into the running XOR
    # A valid original exists iff that total parity is 0.
    return x == 0

function doesValidArrayExist(derived) {
  // Each original[i] appears in two derived terms, so the XOR
  // of all derived values cancels every original[i] pairwise.
  let x = 0;
  for (const v of derived) {
    x ^= v;                // fold the next derived bit into the running XOR
  }
  // A valid original exists iff that total parity is 0.
  return x === 0;
}

boolean doesValidArrayExist(int[] derived) {
    // Each original[i] appears in two derived terms, so the XOR
    // of all derived values cancels every original[i] pairwise.
    int x = 0;
    for (int v : derived) {
        x ^= v;            // fold the next derived bit into the running XOR
    }
    // A valid original exists iff that total parity is 0.
    return x == 0;
}

bool doesValidArrayExist(vector<int>& derived) {
    // Each original[i] appears in two derived terms, so the XOR
    // of all derived values cancels every original[i] pairwise.
    int x = 0;
    for (int v : derived) {
        x ^= v;            // fold the next derived bit into the running XOR
    }
    // A valid original exists iff that total parity is 0.
    return x == 0;
}

Explanation

The trick is to look at what happens when you XOR every value of derived together. Each derived[i] equals original[i] ⊕ original[i+1] (with the last one wrapping back to original[0]).

Lay the terms out: (o₀⊕o₁) ⊕ (o₁⊕o₂) ⊕ … ⊕ (oₙ₋₁⊕o₀). Every original[i] shows up in exactly two of these terms — once as a left operand and once as a right operand — and since a ⊕ a = 0, all of them cancel out.

That means the XOR of all derived values is always 0 whenever a valid original exists. Conversely, if the running XOR comes out non-zero, no binary original can possibly produce it. So the whole problem collapses to a single parity check.

We sweep through derived once, folding each bit into a running accumulator x with x ^= v. At the end we return x == 0. There is nothing to reconstruct — the parity alone is a complete proof of existence.

Example: derived = [1, 1, 0] folds to 1 ⊕ 1 ⊕ 0 = 0, so the answer is true. For derived = [1, 0] the fold is 1 ⊕ 0 = 1 ≠ 0, so the answer is false.

Time: O(n) Space: O(1)