题目

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

解题思路

首先，异或运算可移项性：a ^ b = c 可移项为 a = b ^ c，移项时无需改变符号。

那么 $derived[i]=original[i]⊕original[i+1]$ 改写为 $original[i+1]=original[i]⊕derived[i]$。

于是，我们假设orgininal的首项为0或1，以此递推出original完整的数列。

最后用这个公式验证$derived[n−1]=original[n−1]⊕original[0]$，如果验证出的$derived[n−1]$和给的数列的末项相同，则可判断这个数列存在，反之则不存在。因为这是个递推公式，所以我们实际不需要维护一个数组，维护original递推到的值集合，又因为首项就为0或1，所以也不用保存首项。

其次，对于这道题，首项为0和首项为1的数列是等价的，假如最后推出[0,0,1,1]是一个true数列，那么[1,1,0,0]也一定是一个true数列，这点可以去看异或的真值表。

因此，我们只需要验证首项为0的情况即可，这就又减半了复杂度。因为这题返回的结果类型是bool，那么我们可以将我们计算出来的$dervied[n-1]$和真的$dervied[n-1]$进行异或，相同的话结果就是0（对应答案true），不同则是1（对应答案false），那么再将这个结果与1异或即可，即$original[n−1]⊕original0⊕derived[n−1]⊕1$，简化为 $original[n−1]⊕derived[n−1]⊕1$。

具体代码

class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {

        int orginal = 0;  // 0和1在判断这道题上等价，并且不用新建数组
        int n = derived.size();

        for(int i = 0; i < n - 1; i++)
            orginal = orginal ^ derived[i];
        
        return orginal ^ 1 ^ derived[n - 1];  // 实际上是 orginal ^ 0 ^ derived[n - 1] ^ 1
    }
};