What is the key insight for solving Neighboring Bitwise XOR?

The main insight is that each original element appears in exactly two XOR operations, so the cumulative XOR of derived must be zero for a valid original array.

Can I reconstruct the original array to check?

Explicit reconstruction is unnecessary; a single pass cumulative XOR check suffices and is more efficient.

How does array length affect the solution?

For length 1, derived[0] must be zero. Otherwise, the standard cumulative XOR check works for any n up to 10^5.

Does the circular property matter?

Yes, derived is defined circularly, so derived[n-1] = original[n-1] XOR original[0]; forgetting this leads to incorrect results.

Which pattern does this problem exemplify?

This is a classic Array plus Bit Manipulation pattern where XOR properties are used to validate constraints efficiently.

#2683

Medium

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

LeetCode 题解工作台

相邻值的按位异或

下标从 0 开始、长度为 n 的数组 derived 是由同样长度为 n 的原始二进制数组 original 通过计算相邻值的按位异或（⊕）派生而来。特别地，对于范围 [0, n - 1] 内的每个下标 i ：如果 i = n - 1 ，那么 derived[i] = original[i…

数组位运算

题目描述

下标从 0 开始、长度为 n 的数组 derived 是由同样长度为 n 的原始 二进制数组 original 通过计算相邻值的 按位异或（⊕）派生而来。

特别地，对于范围 [0, n - 1] 内的每个下标 i ：

如果 i = n - 1 ，那么 derived[i] = original[i] ⊕ original[0]
否则 derived[i] = original[i] ⊕ original[i + 1]

给你一个数组 derived ，请判断是否存在一个能够派生得到 derived 的 有效原始二进制数组 original 。

如果存在满足要求的原始二进制数组，返回 true ；否则，返回 false 。

二进制数组是仅由 0 和 1 组成的数组。

示例 1：

输入：derived = [1,1,0]
输出：true
解释：能够派生得到 [1,1,0] 的有效原始二进制数组是 [0,1,0] ：
derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1 
derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1
derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0

示例 2：

输入：derived = [1,1]
输出：true
解释：能够派生得到 [1,1] 的有效原始二进制数组是 [0,1] ：
derived[0] = original[0] ⊕ original[1] = 1
derived[1] = original[1] ⊕ original[0] = 1

示例 3：

输入：derived = [1,0]
输出：false
解释：不存在能够派生得到 [1,0] 的有效原始二进制数组。

提示：

n == derived.length
1 <= n <= 10⁵
derived 中的值不是 0 就是 1 。

lightbulb

解题思路

方法一：位运算

我们不妨假设原始二进制数组为 $a$ ，派生数组为 $b$ ，那么有：

b_0 = a_0 \oplus a_1 \\ b_1 = a_1 \oplus a_2 \\ \cdots \\ b_{n-1} = a_{n-1} \oplus a_0

由于异或运算满足交换律和结合律，因此有：

b_0 \oplus b_1 \oplus \cdots \oplus b_{n-1} = (a_0 \oplus a_1) \oplus (a_1 \oplus a_2) \oplus \cdots \oplus (a_{n-1} \oplus a_0) = 0

因此，只要派生数组的所有元素的异或和为 $0$ ，就一定存在一个满足要求的原始二进制数组。

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

1

2

3

4

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        return reduce(xor, derived) == 0

speed

复杂度分析

指标	值
时间	complexity is O(n) because each element is visited exactly once. Space complexity is O(1) as no extra arrays are needed; only a running XOR accumulator is required.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Watch for understanding that each original element participates in two XOR operations.
question_mark
Check if candidate handles circular array indexing correctly.
question_mark
Ensure the solution does not attempt exhaustive original array construction, which is unnecessary.

warning

常见陷阱

外企场景

error
Forgetting that XORing the same element twice cancels it out in cumulative XOR checks.
error
Neglecting the circular property when computing derived[n-1] XOR original[0].
error
Attempting to reconstruct original array explicitly, which wastes time and space.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of binary arrays, consider arrays with small integer values, still using neighboring XOR constraints.
arrow_right_alt
Allow derived arrays to have unknown entries represented by -1 and check if any valid original exists.
arrow_right_alt
Compute the number of possible original arrays that can generate the given derived array.

help

常见问题

外企场景

继续练习

#2680 最大或值 #2708 一个小组的最大实力值 #2657 找到两个数组的前缀公共数组