#2683

Neighboring Bitwise XOR

pupil · 445 · lc medium +26 · verified · 79.8% accepted · 803 likes · top 91%

Description

A binary array original generates derived where derived[i] = original[i] XOR original[i+1] for i < n-1 and derived[n-1] = original[n-1] XOR original[0]. Given derived, determine whether any valid binary original exists. Return true if so, false otherwise.

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] &oplus; original[1] = 0 &oplus; 1 = 1

derived[1] = original[1] &oplus; original[2] = 1 &oplus; 0 = 1

derived[2] = original[2] &oplus; original[0] = 0 &oplus; 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] &oplus; original[1] = 1

derived[1] = original[1] &oplus; original[0] = 1

Example 3:

Input: derived = [1,0]

Output: false

Explanation: There is no valid original array that gives derived.

Code

1

2

3

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

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