https://leetcode.com/problems/neighboring-bitwise-xor
2683. Neighboring Bitwise XOR
给定一长度为n的阵列derived
此阵列为长度为n的二进制阵列original的相邻元素经由xor运算的结果
运算规则如下:
if index == n-1:
derived[i] = original[i] ^ original[0]
else:
derived[i] = original[i] ^ original[i+1]
请判断是否存在有效的original
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
思路:
以例二为例
derived[0] = original[0] ⊕ original[1] = 1
derived[1] = original[1] ⊕ original[0] = 1
derived[0] ^ derived[1] =
original[0] ⊕ original[1] ^ original[1] ⊕ original[0]
相同元素的xor会抵消 所以结果必为零
我们只要检查derived所有元素的xor是不是0就有答案了
Python Code:
class Solution:
def doesValidArrayExist(self, derived: List[int]) -> bool:
result = 0
for n in derived:
result ^= n
if result == 1:
return False
else:
return True