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.

#1734

Medium

auto_awesome数组·结合·位运算·操作

LeetCode 题解工作台

解码异或后的排列

给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个奇数。它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说，如果 perm = [1,3,2] ，那么 encoded =…

数组位运算

题目描述

给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个奇数。

它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说，如果 perm = [1,3,2] ，那么 encoded = [2,1] 。

给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一。

示例 1：

输入：encoded = [3,1]
输出：[1,2,3]
解释：如果 perm = [1,2,3] ，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]

示例 2：

输入：encoded = [6,5,4,6]
输出：[2,4,1,5,3]

提示：

3 <= n < 10⁵
n 是奇数。
encoded.length == n - 1

lightbulb

解题思路

方法一：位运算

我们注意到，数组 $perm$ 是前 $n$ 个正整数的排列，因此 $perm$ 的所有元素的异或和为 $1 \oplus 2 \oplus \cdots \oplus n$ ，记为 $a$ 。而 $encode[i]=perm[i] \oplus perm[i+1]$ ，如果我们将 $encode[0],encode[2],\cdots,encode[n-3]$ 的所有元素的异或和记为 $b$ ，则 $perm[n-1]=a \oplus b$ 。知道了 $perm$ 的最后一个元素，我们就可以通过逆序遍历数组 $encode$ 求出 $perm$ 的所有元素。

时间复杂度 $O(n)$ ，其中 $n$ 为数组 $perm$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

error
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].
error
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.
error
Building the array with the wrong recurrence direction, because perm[i + 1] must be perm[i] XOR encoded[i], not the other way around.

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1738 找出第 K 大的异或坐标值 #1723 完成所有工作的最短时间 #1720 解码异或后的数组