Decode XORed Array: XOR Inverse Property

You are given an integer array encoded of length n and an integer first. There is a hidden array arr of length n + 1 where encoded[i] = arr[i] XOR arr[i + 1]. You also know that arr[0] = first. Return the original array arr.

This is LeetCode 1720: Decode XORed Array, an easy-level problem that tests whether you understand a fundamental property of XOR: it is its own inverse.

Why this problem matters

XOR shows up constantly in coding interviews, but many candidates only know it from the classic "single number" problem. Decode XORed Array forces you to use XOR in reverse, recovering data from an encoded sequence. That skill transfers directly to problems involving checksums, stream decoding, and parity-based reconstruction.

Understanding that XOR is invertible also builds intuition for harder bit manipulation problems. Once you internalize that a ^ b ^ a = b, you start seeing it as a toggle or undo operation, not just a mysterious bitwise trick. This problem is one of the cleanest ways to drill that idea.

The key insight

The encoding formula is encoded[i] = arr[i] XOR arr[i+1]. If you XOR both sides by arr[i], you get arr[i+1] = encoded[i] XOR arr[i]. This works because XOR is its own inverse. Applying it twice cancels out: x ^ x = 0 and 0 ^ y = y.

Since we already know arr[0] = first, we have our starting point. From there, each element in the encoded array gives us exactly what we need to compute the next element of arr. The entire hidden array unzips left to right in a single pass.

The algorithm:

1. Initialize result array with first as the first element.
2. For each encoded value, XOR it with the previous decoded value to get the next element.
3. Return the result array.

The solution

def decode(encoded: list[int], first: int) -> list[int]:
    arr = [first]
    for val in encoded:
        arr.append(arr[-1] ^ val)
    return arr

The function starts by placing first into the result array. Then it walks through each value in encoded, XOR-ing it with the most recently decoded element to produce the next one. The ^ operator in Python performs bitwise XOR.

Notice how little code this requires. There are no nested loops, no auxiliary data structures, and no special cases. The XOR inverse property does all the heavy lifting. You read one encoded value, apply one XOR, and append the result.

This pattern of "seed plus sequential decoding" appears in many contexts beyond this specific problem. Anytime you have a reversible transformation applied to consecutive pairs, you can unwind it from one known endpoint. XOR just happens to be one of the simplest reversible operations.

Visual walkthrough

Let's trace through the full decode with first = 1 and encoded = [1, 2, 3]. At each step, we XOR the latest encoded value with the previous decoded element to reveal the next entry in the hidden array.

By the end of step 4, the entire array [1, 0, 2, 1] is recovered. Each step relies only on the element decoded immediately before it, which is why a single left-to-right pass is all you need.

Complexity analysis

Time: We iterate through the encoded array once, performing a constant-time XOR at each position. That gives us O(n) where n is the length of the encoded array.

Space: We build the output array of length n + 1. If you count the output as required space, there is no additional allocation beyond it. The algorithm uses O(1) extra space on top of the output.

The building blocks

1. XOR as its own inverse

The property a ^ b ^ a = b means XOR can undo itself. If you know the result of a ^ b and you know a, you can recover b by XOR-ing one more time. This is the single fact that makes the entire problem solvable.

encoded_val = a ^ b
b_recovered = encoded_val ^ a  # gives back b

This pattern appears whenever data has been "encrypted" or "encoded" with XOR. The same operation that encodes also decodes. No separate inverse function is needed.

2. Sequential decoding from a seed value

When you have a chain of dependent values and one known starting point, you can reconstruct the entire sequence by iterating forward. The seed unlocks the next value, which unlocks the one after that, and so on.

result = [seed]
for step in transforms:
    result.append(apply(result[-1], step))

This shows up in prefix sum reconstruction, linked list traversal, and any problem where each element depends on its predecessor. The key requirement is that the transformation is reversible, which XOR satisfies perfectly.

Edge cases

• Single encoded element: When encoded has just one value, the result is [first, first ^ encoded[0]]. The algorithm handles this naturally with no special logic.
• All zeros in encoded: If every encoded value is 0, then arr[i+1] = arr[i] ^ 0 = arr[i]. The result is an array where every element equals first.
• first = 0: XOR with 0 is the identity, so arr[1] = encoded[0] ^ 0 = encoded[0]. The algorithm still works correctly because 0 ^ x = x.
• Large values: XOR operates on individual bits regardless of magnitude. Values up to 10^5 (within the problem constraints) are well within standard integer range, so overflow is never a concern.

From understanding to recall

Reading through the XOR inverse property is the easy part. The harder part is recognizing when to apply it under interview pressure. When you see a problem that says "encoded with XOR" or "recover the original from XOR differences," the pattern needs to fire automatically.

The way to bridge that gap is repetition at spaced intervals. You practice the seed-plus-decode pattern as an isolated building block, then revisit it a day later, then three days after that. Each repetition strengthens the retrieval path until it becomes reflexive.

Related posts

• Single Number - The foundational XOR problem where XOR cancellation reveals the unique element
• Missing Number - Using XOR to find what is absent from a sequence
• Single Number III - Advanced XOR technique that separates two unique numbers using bit properties

XOR is one of those operations that feels alien at first but becomes second nature with practice. CodeBricks breaks bit manipulation into these small, durable building blocks and schedules reviews so each pattern sticks permanently.