Decode XORed Permutation: XOR Properties for Recovery

LeetCode Decode XORed Permutation (Problem 1734) gives you an integer array encoded of length n - 1, where encoded[i] = perm[i] XOR perm[i+1]. The array perm is a permutation of the first n positive integers, and n is always odd. Your job is to recover the original perm array using only the encoded values.

Unlike the simpler Decode XORed Array problem (LeetCode 1720), you are not given the first element directly. You need to figure out perm[0] yourself. The constraint that n is odd is the crucial piece that makes this possible.

Why this problem matters

XOR recovery problems test whether you can exploit algebraic properties of bitwise operations under pressure. Many candidates know that a ^ a = 0 and a ^ 0 = a, but few can combine those identities with structural constraints (like "the array is a permutation of 1..n") to derive a missing value. This problem sits right at that intersection.

The technique here also generalizes well. Anytime you know the XOR of a full set and can compute the XOR of a subset, you can recover whatever is missing. That pattern shows up in error detection, cryptographic protocols, and other interview problems where partial information needs to be combined to reconstruct the whole.

Finally, this problem rewards careful index reasoning. You need to understand exactly which elements of perm get covered when you XOR together odd-indexed entries of encoded. Getting that mapping right is the difference between a clean solution and a debugging spiral.

The key insight

We know that perm is a permutation of [1, 2, ..., n]. That means the XOR of all elements in perm is simply 1 ^ 2 ^ 3 ^ ... ^ n. Call this total_xor.

Now look at what happens when you XOR together the odd-indexed entries of encoded:

• encoded[1] = perm[1] ^ perm[2]
• encoded[3] = perm[3] ^ perm[4]
• encoded[5] = perm[5] ^ perm[6]
• ... and so on.

Because n is odd, the encoded array has even length (n - 1), so the odd indices 1, 3, 5, ... cover pairs (perm[1], perm[2]), (perm[3], perm[4]), ... all the way through (perm[n-2], perm[n-1]). Together, these pairs include every element of perm except perm[0].

Call this odd_xor = encoded[1] ^ encoded[3] ^ ... = perm[1] ^ perm[2] ^ ... ^ perm[n-1].

Now you can isolate perm[0]:

perm[0] = total_xor ^ odd_xor

The elements perm[1] through perm[n-1] appear in both total_xor and odd_xor, so they cancel out, leaving only perm[0]. Once you have perm[0], decoding the rest is just perm[i+1] = perm[i] ^ encoded[i].

The solution

def decode(encoded: list[int]) -> list[int]:
    n = len(encoded) + 1
    total_xor = 0
    for i in range(1, n + 1):
        total_xor ^= i

    odd_xor = 0
    for i in range(1, len(encoded), 2):
        odd_xor ^= encoded[i]

    perm = [0] * n
    perm[0] = total_xor ^ odd_xor

    for i in range(len(encoded)):
        perm[i + 1] = perm[i] ^ encoded[i]

    return perm

The first loop computes the XOR of all integers from 1 to n. The second loop XORs the odd-indexed encoded values to get the XOR of every element except perm[0]. The third loop decodes the remaining elements left to right, each one depending only on the previous element and the corresponding encoded value.

There is no sorting, no hash map, no recursion. Three simple passes and a handful of XOR operations reconstruct the entire permutation.

Visual walkthrough

Let's trace through the algorithm with encoded = [6, 5, 4, 6], which means n = 5 and perm is some permutation of [1, 2, 3, 4, 5].

Each step builds on the previous one. The first two steps gather the information needed to compute perm[0]. Step 3 combines them via XOR cancellation. Step 4 unzips the rest of the array in a single forward pass.

Complexity analysis

Time: Three linear passes over arrays of length at most n. Each pass does constant work per element, giving O(n) total.

Space: The output array perm uses O(n) space. Beyond that, we only use a few integer variables, so there is no additional allocation.

The building blocks

1. XOR cancellation

The property a ^ a = 0 is the foundation. When you XOR a complete set with a subset that is missing one element, every shared element cancels. The missing element is the only thing left.

# If full_xor = a ^ b ^ c and partial_xor = b ^ c
# then full_xor ^ partial_xor = a ^ b ^ c ^ b ^ c = a
missing = full_xor ^ partial_xor

This pattern appears in Single Number, Missing Number, and many other problems where one value needs to be isolated from a group.

2. Partial XOR recovery

The trick of XORing odd-indexed encoded values to cover a specific subset of perm is a clever application of how encoded pairs expand. Each encoded[i] contributes exactly perm[i] ^ perm[i+1]. By choosing non-overlapping pairs (odd indices), you cover all elements except the first without any double-counting.

# encoded[1] = perm[1] ^ perm[2]
# encoded[3] = perm[3] ^ perm[4]
# XOR them: perm[1] ^ perm[2] ^ perm[3] ^ perm[4]
# That's everything except perm[0] (when n is odd)
odd_xor = 0
for i in range(1, len(encoded), 2):
    odd_xor ^= encoded[i]

The requirement that n is odd guarantees the pairs align perfectly to exclude exactly one element.

Edge cases

• n = 1: The encoded array is empty. The only permutation of [1] is [1]. total_xor = 1, odd_xor = 0, so perm[0] = 1.
• n = 3: The encoded array has 2 elements. Only encoded[1] is at an odd index, so odd_xor = encoded[1] = perm[1] ^ perm[2]. Then perm[0] = (1 ^ 2 ^ 3) ^ (perm[1] ^ perm[2]).
• Large n with consecutive XOR patterns: When n is a multiple of 4 minus 1 (like 3, 7, 15), total_xor evaluates to 0 because XOR of 1..n follows a four-cycle pattern. The algorithm handles this correctly since the logic does not depend on the magnitude of total_xor.

From understanding to recall

The "XOR odd-indexed encoded values" trick is the kind of insight that is hard to rediscover under time pressure if you have not seen it before. Reading through the explanation once gives you understanding, but interviews demand recall. You need the pattern to surface automatically when you see "permutation," "XOR," and "encoded."

Spaced repetition closes that gap. You work through the derivation today, then revisit it in two days, then a week later. Each time, the retrieval gets faster. Eventually the approach becomes reflexive: you see a permutation-based XOR encoding, and you immediately think "total XOR minus subset XOR."

Related posts

• Decode XORed Array - Simpler version where first element is given directly
• XOR Operation in an Array - Basic XOR computation practice
• Single Number - The classic XOR cancellation problem

The jump from Decode XORed Array to Decode XORed Permutation captures what makes bit manipulation problems so rewarding. A small structural constraint (odd-length permutation) unlocks an elegant algebraic trick. CodeBricks breaks these techniques into small building blocks and schedules reviews so each insight becomes permanent knowledge, not a one-time read.