异或运算的运用

题目链接：https://leetcode.cn/problems/neighboring-bitwise-xor/description/?envType=daily-question&envId=2025-07-31

题目 - 相邻值的按位异或

下标从 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

分析

问题定义：

给定数组 derived，判断是否存在一个数组 original，满足：

异或性质应用：

异或的性质：

交换律：
结合律：

异或两边求和：

将所有 derived[i] 的值进行异或：

化简右边：

我们将所有 original[i] 的项列出来（注意重复次数）：

original[0] 出现 2 次
original[1] 出现 2 次
…
original[n-1] 出现 2 次

所以：

因为每个 original[i] 都被异或了两次。

最终结论的数学表达式：

$存在合法的数组$

这就推导结论的最终数学表达形式。

所以我们对derived循环求异或，判断得到的值是否为0即可。

代码

1
2
3

var doesValidArrayExist = function(derived) {
    return derived.reduce((xor, x) => xor ^ x, 0) === 0;
};