We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Neighboring Bitwise XOR

Number: 2792

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an array derived of length n, where derived[i] is the XOR of two adjacent elements of a binary array original (with the rule that derived[n-1] = original[n-1] XOR original[0]), determine if there exists a valid binary array original that can generate the derived array.

Key Insights

  • The original array elements are either 0 or 1.
  • Constructing the original array based on an assumed starting value (either 0 or 1) leads to a cyclic dependency.
  • By successively XOR’ing the starting value with the derived elements, the computed last element must equal the starting value.
  • This boils down to checking whether the XOR of all derived elements is 0 (for cases when n > 1). For n == 1, ensure that derived[0] is 0.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the derived array. Space Complexity: O(1) as only a constant amount of extra space is used.

Solution

We can solve the problem by realizing that if we pick an initial value for original[0], then we can compute the rest of the original array, because:

  1. original[1] = original[0] XOR derived[0]
  2. original[2] = original[1] XOR derived[1] = original[0] XOR derived[0] XOR derived[1]
  3. Continue this process until original[n-1].
  4. Finally, because the array is circular, derived[n-1] = original[n-1] XOR original[0]. This leads to the equation: original[0] XOR (derived[0] XOR derived[1] ... XOR derived[n-1]) == original[0]
  5. Cancelling out original[0] from both sides, we obtain that the XOR of all derived elements must be 0.

Thus, if the XOR of all values in derived is 0, a valid binary original array exists.

The algorithm is simple:

  • If n == 1, return true if derived[0] is 0, otherwise false.
  • For n > 1, check if reduce(XOR) across all elements equals 0.

Code Solutions

# Python solution for the Neighboring Bitwise XOR problem

class Solution:
    def doesValidArrayExist(self, derived: list[int]) -> bool:
        # Handle case when there's only one element in derived.
        if len(derived) == 1:
            return derived[0] == 0
        
        # Calculate the XOR sum of all elements in the derived array.
        xor_sum = 0
        for value in derived:
            xor_sum ^= value  # Bitwise XOR
        
        # For a valid original array, the XOR sum should be 0.
        return xor_sum == 0

# Example usage:
# solution = Solution()
# print(solution.doesValidArrayExist([1, 1, 0]))  # Expected output: True
← Back to All Questions