2683. Neighboring Bitwise XOR

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

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

Approach 01:

#include <vector>
#include <numeric>
#include <functional>

class Solution {
public:
    bool doesValidArrayExist(const std::vector<int>& derivedArray) {
        // Calculate the cumulative XOR of all elements in derivedArray
        int cumulativeXor = std::accumulate(derivedArray.begin(), derivedArray.end(), 0, std::bit_xor<int>());
        // A valid original array exists if the cumulative XOR is zero
        return cumulativeXor == 0;
    }
};

from typing import List
from functools import reduce
import operator

class Solution:
    def doesValidArrayExist(self, derivedArray: List[int]) -> bool:
        # Calculate the cumulative XOR of all elements in derivedArray
        cumulativeXor = reduce(operator.xor, derivedArray)
        # A valid original array exists if the cumulative XOR is zero
        return cumulativeXor == 0

Time Complexity:

• Cumulative XOR Calculation:

  We use the std::accumulate function to compute the cumulative XOR of the elements in derivedArray, which requires a single pass through the array. This operation takes \( O(n) \), where \( n \) is the size of derivedArray.

• Overall Time Complexity:

  The total time complexity is \( O(n) \).

Space Complexity:

• Auxiliary Space:

  The algorithm uses only a single integer variable cumulativeXor to store intermediate results, resulting in \( O(1) \) auxiliary space usage.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).