2683-相邻值的按位异或

下标从 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 <= 105
• derived 中的值不是 0 就是 1 。

下午两点【biIibiIi@灵茶山艾府】 直播讲题，记得关注哦~

---

前置知识：异或运算的性质

a\oplus a = 0。

a\oplus b = c 两边同时异或 a 可以得到 b = c\oplus a。

思路

如果知道 original}[0]，利用 derived}[i] 可以推出其余 original}[i] 的值，即

\textit{original}[i+1] = \textit{original}[i]\oplus \textit{derived}[i]

那么有

\textit{original}[n-1] = \textit{original}[0] \oplus \textit{derived}[0] \oplus \textit{derived}[1] \cdots \oplus \textit{derived}[n-2]

由于

\textit{original}[0]\oplus \textit{original}[n-1] =\textit{derived}[n-1]

联立得

\textit{derived}[0] \oplus \textit{derived}[1] \cdots \oplus \textit{derived}[n-1] = 0

所以如果上式成立，original 必然存在。

[sol1-Python3]

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

[sol1-Go]

func doesValidArrayExist(derived []int) bool {
	xor := 0
	for _, x := range derived {
		xor ^= x
	}
	return xor == 0
}

复杂度分析

• 时间复杂度：\mathcal{O}(n)，其中 n 为 derived 的长度。
• 空间复杂度：\mathcal{O}(1)。仅用到若干额外变量。