Neighboring Bitwise XOR

main.md

Question

Approach

To solve the problem, I started by assuming two possible values for the first element of the original array: 0 and 1. Using the formula:

original[i+1] = derived[i] ⊕ original[i]

I then iteratively computed the rest of the elements in the original array for each assumption. After constructing the array, I verified the circular condition:

original[-1] ⊕ original[0] = derived[-1]

to ensure the derived array's validity. If the condition was satisfied for either assumption, I returned True. If neither worked, I concluded that no valid original array could exist and returned False.

Implementation

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

        original = [0] * n
        for i in range(1, n):
            original[i] = derived[i - 1] ^ original[i - 1]

        if (original[-1] ^ original[0]) == derived[-1]:
            return True

        original[0] = 1
        for i in range(1, n):
            original[i] = derived[i - 1] ^ original[i - 1]

        if (original[-1] ^ original[0]) == derived[-1]:
            return True

        return False

Complexities

• Time: O(n), as the algorithm makes a single pass through the array for each assumption.
• Space: O(n), for the original array.