What is the simplest method to decode a XORed array?

Start with the given first element and iteratively compute arr[i+1] = encoded[i] XOR arr[i]. This method ensures accurate reconstruction.

Does the solution require extra memory beyond the output array?

No, only the array to store the reconstructed arr is necessary; no additional data structures are required.

Can this approach handle the maximum constraints of n = 104?

Yes, the O(n) time and O(n) space approach scales efficiently even for arrays of length 104.

What are common mistakes when solving Decode XORed Array?

Off-by-one indexing, confusing XOR with addition, and using unnecessary loops or extra arrays are frequent errors.

Is there a shortcut to verify if the decoded array is correct?

Recompute encoded by XORing consecutive elements of the reconstructed arr; it should match the original encoded array.

#1720

Easy

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

LeetCode 题解工作台

解码异或后的数组

未知整数数组 arr 由 n 个非负整数组成。经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如， arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。给你编码后…

数组位运算

题目描述

未知整数数组 arr 由 n 个非负整数组成。

经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。

给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。

请解码返回原数组 arr 。可以证明答案存在并且是唯一的。

示例 1：

输入：encoded = [1,2,3], first = 1
输出：[1,0,2,1]
解释：若 arr = [1,0,2,1] ，那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

示例 2：

输入：encoded = [6,2,7,3], first = 4
输出：[4,2,0,7,4]

提示：

2 <= n <= 10⁴
encoded.length == n - 1
0 <= encoded[i] <= 10⁵
0 <= first <= 10⁵

lightbulb

解题思路

方法一：位运算

根据题目描述，有：

\textit{encoded}[i] = \textit{arr}[i] \oplus \textit{arr}[i + 1]

如果我们将等式两边同时异或上 $\textit{arr}[i]$ ，那么就会得到：

\textit{arr}[i] \oplus \textit{arr}[i] \oplus \textit{arr}[i + 1] = \textit{arr}[i] \oplus \textit{encoded}[i]

即：

\textit{arr}[i + 1] = \textit{arr}[i] \oplus \textit{encoded}[i]

根据上述推导，我们可以从 $\textit{first}$ 开始，依次计算出数组 $\textit{arr}$ 的每一个元素。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组的长度。

1

2

3

4

5

6

7

class Solution:
    def decode(self, encoded: List[int], first: int) -> List[int]:
        ans = [first]
        for e in encoded:
            ans.append(ans[-1] ^ e)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) since each encoded element is processed exactly once. Space complexity is O(n) for storing the reconstructed arr. No additional overhead is required beyond the output array.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Watch for off-by-one errors in indexing while reconstructing arr using XOR.
question_mark
Expect candidates to apply arr[i+1] = encoded[i] XOR arr[i] directly without extra data structures.
question_mark
Check understanding of bit manipulation patterns and sequential array reconstruction.

warning

常见陷阱

外企场景

error
Incorrectly starting reconstruction from the wrong index, leading to all subsequent values being wrong.
error
Confusing XOR with addition or other bitwise operations, resulting in wrong output.
error
Allocating extra arrays or using unnecessary loops that increase time or space complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
The array may contain larger integers up to 10^6 to test handling of bigger numbers with XOR.
arrow_right_alt
Provide multiple first elements or partial arr segments and ask for reconstruction of the remaining array.
arrow_right_alt
Encode arr with a different bitwise operator, such as AND or OR, to test understanding of operator-specific reconstruction.

help

常见问题

外企场景

继续练习

#1723 完成所有工作的最短时间 #1707 与数组中元素的最大异或值 #1734 解码异或后的排列