1720. Decode XORed Array
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 85.1%
Problem Breakdown
The problem requires us to decode an array arr from its encoded form encoded. The encoding process involves XORing consecutive elements of arr to produce the encoded array. Specifically, encoded[i] = arr[i] XOR arr[i + 1]. We are given the first element of arr, and we need to reconstruct the entire array.
Inputs:
encoded: An integer array of lengthn - 1.first: The first element of the original arrayarr.
Outputs:
- The decoded array
arrof lengthn.
Implicit Constraints:
- The length of
arris one more than the length ofencoded. - All elements in
arrandencodedare non-negative integers. - The solution is guaranteed to exist and be unique.
Intuition
A brute-force approach would involve trying all possible combinations for the remaining elements of arr, which is computationally expensive. Instead, we can leverage the properties of XOR to decode the array efficiently.
The key insight is that XOR is its own inverse: a XOR b XOR a = b. This means if we know encoded[i] and arr[i], we can find arr[i + 1] by computing arr[i + 1] = encoded[i] XOR arr[i].
Starting with the given first element, we can iteratively decode each subsequent element using this property.
Approach
- Initialize an array
arrof lengthn(wherenis one more than the length ofencoded). - Set the first element of
arrto the givenfirst. - Iterate through the
encodedarray:- For each index
i, computearr[i + 1] = encoded[i] XOR arr[i].
- For each index
- Return the decoded array
arr.
This approach leverages the associative and commutative properties of XOR, allowing us to decode the array in a single pass with linear time complexity.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the original array
arr. We iterate through theencodedarray once. - Space Complexity: O(n) for storing the decoded array
arr.
Solution
def decode(encoded, first):
# Initialize the result array with the given first element
arr = [first]
# Decode each subsequent element using XOR
for i in range(len(encoded)):
arr.append(encoded[i] ^ arr[i])
return arr
Edge Cases Handled
- Single Element Array: If
encodedis empty, the function correctly returns an array with just thefirstelement. - All Elements Zero: The XOR operation handles cases where all elements are zero without any issues.
- Maximum Values: The solution works efficiently even when elements are at the upper limit of their range (
10^5).