#1734

Medium

LeetCode Problem Workspace

Decode XORed Permutation

Decode XORed Permutation uses prefix reconstruction with global XOR to recover the hidden odd-length permutation in linear time.

array bit manipulation

Problem Statement

You are given an array encoded built from an unknown permutation perm of the integers from 1 to n, where n is odd. Each entry stores the XOR of two neighbors, so encoded[i] equals perm[i] XOR perm[i + 1], and the array has length n - 1.

Your task is to reconstruct and return the original permutation. The input is guaranteed to come from exactly one valid permutation, so the main challenge is not ambiguity but finding the one missing starting value that lets the XOR chain unfold correctly across the array.

Examples

Example 1

Input: encoded = [3,1]

Output: [1,2,3]

If perm = [1,2,3], then encoded = [1 XOR 2,2 XOR 3] = [3,1]

Example 2

Input: encoded = [6,5,4,6]

Output: [2,4,1,5,3]

Example details omitted.

Constraints

3 <= n < 105
n is odd.
encoded.length == n - 1

Solution Approach

Use odd-length structure to isolate the first value

Let n be encoded.length + 1. First compute total = 1 XOR 2 XOR ... XOR n, which is the XOR of every value in perm because perm is a permutation. Then compute oddEncoded = encoded[1] XOR encoded[3] XOR encoded[5] ... . This works because each chosen encoded term cancels adjacent permutation values in a way that leaves perm[1] XOR perm[2] XOR ... XOR perm[n - 1]. XOR that with total to get perm[0].

Rebuild the permutation from left to right

Once perm[0] is known, the rest is mechanical. Since encoded[i] = perm[i] XOR perm[i + 1], rearrange it to perm[i + 1] = perm[i] XOR encoded[i]. Walk through encoded once, append each next value, and the full permutation appears without any branching or backtracking.

Why this beats brute force guessing

A tempting mistake is to guess the first number and check whether the reconstruction stays inside 1..n without duplicates. That adds unnecessary bookkeeping and can degrade into a validation-heavy approach. The XOR identity removes guessing entirely, and the odd n guarantee is exactly what makes the alternating encoded XOR expose enough information to solve the start value directly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The optimal solution runs in O(n) time because it makes a constant number of linear passes: one for XORing 1 through n, one for every other encoded value, and one to rebuild perm. It uses O(1) extra space beyond the output array, since the key work is done with a few running XOR variables.

What Interviewers Usually Probe

They mention that n is odd, which is the clue that alternating encoded positions reveal all permutation values except the first.
They hint at XOR from 1 to n, pushing you to combine permutation-wide XOR with local neighbor XOR relationships.
They care whether you can derive perm[0] mathematically instead of guessing and validating candidates.

Common Pitfalls or Variants

Common pitfalls

XORing the wrong encoded indices, such as starting at index 0 instead of index 1, which breaks the cancellation pattern needed to isolate perm[0].
Forgetting that the answer is a permutation of 1 through n, so total XOR must be computed from that full range, not from encoded values.
Building the array with the wrong recurrence direction, because perm[i + 1] must be perm[i] XOR encoded[i], not the other way around.

Follow-up variants

Return the same permutation when encoded is streamed, requiring you to delay reconstruction until perm[0] is derived from the full alternating XOR.
Decode a related array where the original numbers are distinct but not guaranteed to be 1 through n, removing the direct total XOR shortcut.
Handle the non-odd case and explain why this exact alternating-XOR trick no longer isolates a single starting value.

FAQ

What is the key idea in Decode XORed Permutation?

The key is to recover perm[0] without guessing. XOR all integers from 1 to n, then XOR encoded at odd indices to get the XOR of every permutation value except the first, and combine those results to isolate perm[0].

Why does the problem require n to be odd?

The odd length makes the alternating XOR over encoded line up so that all values except perm[0] remain after cancellation. Without odd n, this exact parity-based extraction does not produce the missing starting value cleanly.

Why do we XOR numbers from 1 to n instead of only using encoded?

Because perm is a permutation of 1 through n, XORing that full range gives the XOR of every value in perm. Encoded alone only tells you neighbor relationships, so you need the full-range XOR to anchor the reconstruction.

Is there a simpler brute force approach for this Array plus Bit Manipulation pattern?

You could try every possible first value and rebuild the array, but that adds duplicate checks and wastes the structure the problem gives you. The intended XOR method is cleaner, deterministic, and linear.

How do I verify the recurrence after finding the first number?

Use the identity encoded[i] = perm[i] XOR perm[i + 1]. Rearranging gives perm[i + 1] = perm[i] XOR encoded[i], so each next value follows directly from the current value and the encoded array.

terminal

Solution

Solution 1: Bitwise Operation

We notice that the array $perm$ is a permutation of the first $n$ positive integers, so the XOR of all elements in $perm$ is $1 \oplus 2 \oplus \cdots \oplus n$, denoted as $a$. And $encode[i]=perm[i] \oplus perm[i+1]$, if we denote the XOR of all elements $encode[0],encode[2],\cdots,encode[n-3]$ as $b$, then $perm[n-1]=a \oplus b$. Knowing the last element of $perm$, we can find all elements of $perm$ by traversing the array $encode$ in reverse order.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def decode(self, encoded: List[int]) -> List[int]:
        n = len(encoded) + 1
        a = b = 0
        for i in range(0, n - 1, 2):
            a ^= encoded[i]
        for i in range(1, n + 1):
            b ^= i
        perm = [0] * n
        perm[-1] = a ^ b
        for i in range(n - 2, -1, -1):
            perm[i] = encoded[i] ^ perm[i + 1]
        return perm

Continue Practicing

#1738 find kth largest xor coordinate value #1723 find minimum time to finish all jobs #1720 decode xored array