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

Decode XORed Array

Number: 1839

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an encoded array, where each encoded[i] represents the XOR of consecutive elements (arr[i] XOR arr[i+1]) of a hidden non-negative integer array arr, and the first element of arr is provided as first, reconstruct the original array arr.

Key Insights

  • The XOR operation is reversible: if a XOR b = c, then a XOR c = b.
  • Since encoded[i] = arr[i] XOR arr[i+1], we can obtain arr[i+1] by computing arr[i] XOR encoded[i].
  • Start with the given first element and iterate through encoded to build the entire original array.

Space and Time Complexity

Time Complexity: O(n), as we iterate over the encoded array once. Space Complexity: O(n), for storing the decoded array.

Solution

We initialize the resulting array arr with the provided first element. Then, for every element in the encoded array, we compute the next element as the XOR of the current element in arr and the corresponding encoded value. This uses the property of XOR, which allows us to recover one operand if the other operand and the result are known.

Code Solutions

# Python solution for Decode XORed Array

class Solution:
    def decode(self, encoded: List[int], first: int) -> List[int]:
        # Initialize the result list with the given first element.
        decoded = [first]
        # Iterate over the encoded list
        for num in encoded:
            # The next element in decoded is the XOR of the last element of decoded and the current encoded element.
            next_val = decoded[-1] ^ num
            decoded.append(next_val)
        return decoded

# Example usage:
# sol = Solution()
# print(sol.decode([1,2,3], 1))  # Output: [1,0,2,1]
← Back to All Questions