相邻值的按位异或

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

// 思路: 使用 Java Stream 对 derived 数组中的所有元素求和，然后判断其是否为偶数。
import java.util.Arrays;

public class Solution {
    public boolean doesValidOriginalExist(int[] derived) {
        // 计算 derived 数组的元素总和
        int sum = Arrays.stream(derived).sum();
        // 如果总和为偶数，则存在有效的原始二进制数组 original
        return sum % 2 == 0;
    }
}

题解的核心思路是利用按位异或的性质来判断是否存在一个符合条件的原始数组。具体地，由于异或操作具有可逆性和自反性（即 a^a=0 且 a^0=a），对派生数组 `derived` 中的所有元素进行连续异或操作后，如果结果为0，说明原始数组 `original` 可能存在。这是因为在派生过程中的异或操作，如果从 `original` 数组派生出 `derived`，最终所有的项异或的结果应该是0。这是因为各个项的异或会在原始数组的首尾项上抵消，即 original[0] ⊕ original[n-1]，如果 `derived` 数组能够由某个数组派生而来，则这个结果必须为0。

O(n)

O(1)