[LeetCode] 2683. Neighboring Bitwise XOR

A 0-indexed array derived with length n is derived by computing the bitwise XOR (⊕) of adjacent values in a binary array original of length n.

Specifically, for each index i in the range [0, n - 1]:
If i = n - 1, then derived[i] = original[i] ⊕ original[0].
Otherwise, derived[i] = original[i] ⊕ original[i + 1].
Given an array derived, your task is to determine whether there exists a valid binary array original that could have formed derived.

Return true if such an array exists or false otherwise.

A binary array is an array containing only 0’s and 1’s

Example 1:
Input: derived = [1,1,0]
Output: true
Explanation: A valid original array that gives derived is [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

Example 2:
Input: derived = [1,1]
Output: true
Explanation: A valid original array that gives derived is [0,1].
derived[0] = original[0] ⊕ original[1] = 1
derived[1] = original[1] ⊕ original[0] = 1

Example 3:
Input: derived = [1,0]
Output: false
Explanation: There is no valid original array that gives derived.

Constraints:
n == derived.length
1 <= n <= 105
The values in derived are either 0’s or 1’s

相邻值的按位异或。

下标从 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 组成的数组。

思路

思路是位运算的前缀和。题目说了 derived 数组是由一个长度相同的二进制数组 original 通过计算相邻值的 按位异或（XOR）派生而来，其中对于任意的 derived[i] 而言，derived[i] = original[i] ⊕ original[i + 1]。那么，

derived[0] = original[0] XOR original[1]
derived[1] = original[1] XOR original[2]
derived[2] = original[2] XOR original[3]
...
derived[n-2] = original[n-2] XOR original[n-1]
derived[n-1] = original[n-1] XOR original[0]

如果我们截取一段更短的做运算，比如如下这一段，假设只有三个元素，那么
derived[0] XOR derived[1] XOR derived[2] 就等于
original[0] XOR original[1] XOR original[1] XOR original[2] XOR original[2] XOR original[0]

其中因为 XOR 是异或操作，两个相同的数字异或等于 0，那么这一段我们把它变一下
original[0] XOR original[0] XOR original[1] XOR original[1] XOR original[2] XOR original[2]，其中两两XOR的结果 = 0，所以如果他们整体 XOR 的结果等于 0 的话，那么就证明 derived 数组是合法的。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        int res = 0;
        for (int d : derived) {
            res ^= d;
        }
        return res == 0;
    }
}