2683. Neighboring Bitwise XOR

Problem

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

https://leetcode.com/problems/neighboring-bitwise-xor/

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 <= 10⁵
• The values in derived are either 0’s or 1’s

Test Cases

1
2

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('derived, expected', [
    ([1,1,0], True),
    ([1,1], True),
    ([1,0], False),
])
@pytest.mark.parametrize('sol', [Solution(), Solution2()])
def test_solution(sol, derived, expected):
    assert sol.doesValidArrayExist(derived) == expected

Thoughts

易知：

• original[1] = original[0] ⊕ derived[0]
• original[2] = original[1] ⊕ derived[1] = original[0] ⊕ derived[0] ⊕ derived[1]
• ……
• original[n-1] = original[n-2] ⊕ derived[n-2] = original[0] ⊕ derived[0] ⊕ derived[1] ⊕ ... ⊕ derived[n-2]
• original[0] = original[n-1] ⊕ derived[n-1] = original[0] ⊕ derived[0] ⊕ derived[1] ⊕ ... ⊕ derived[n-1]

可见先计算 derived 所有数字的异或结果，如果结果为 0，它与 original[0] 异或之后等于 original[0]，说明存在 valid original 数组。否则，original[0] 原本的值与异或之后推导出来的值不相等，说明不存在 valid original 数组。

另一个角度，想让 derived 所有数字的异或结果为 0，它所含的 1 的个数必须是偶数。亦即 derived 中 1 的个数是偶数，存在 valid original 数组，否则不存在。

Code

1
2
3
4
5
6
7

from functools import reduce
import operator


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

1
2
3

class Solution:
    def doesValidArrayExist(self, derived: list[int]) -> bool:
        return sum(derived) & 1 == 0

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章