Problem of The Day: Neighboring Bitwise XOR

Problem Statement

Brute Force [TLE]

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

        def isValid(curr):
            i = 0
            n = len(curr)
            for i in range(1, n, 2):
                next_idx = (i + 1) % n
                if curr[i] != curr[next_idx]:
                    return False
            return True

        @cache
        def helper(i, curr):
            if i == N:
                return isValid(curr)
            if derived[i] == 1:
                return helper(i + 1,  curr + '10') or helper(i + 1, curr + '01')
            return helper(i + 1, curr + '00') or helper(i + 1, curr + '11')


        return helper(0, '')

Editorial

Approach 1: Simulation

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        # Create an original array initialized with 0.
        original = [0]
        for i in range(len(derived)):
            original.append(derived[i] ^ original[i])

        # Store the validation results in checkForZero and checkForOne respectively.
        check_for_zero = original[0] == original[-1]
        original = [1]
        for i in range(len(derived)):
            original.append(derived[i] ^ original[i])
        check_for_one = original[0] == original[-1]

        return check_for_zero or check_for_one

Approach 2: Cumulative XOR

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        XOR = 0
        for element in derived:
            XOR = XOR ^ element
        return XOR == 0

Approach 3: Sum Parity

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        return sum(derived) % 2 == 0