Decode XORed Array

Difficulty: Easy | Acceptance: 87.40% | Paid: No Topics: Array, Bit Manipulation

There is a hidden integer array arr that consists of n non-negative integers.

It was encoded into another integer array encoded of length n - 1, such that encoded[i] = arr[i] XOR arr[i + 1]. For example, if arr = [1,0,2,1], then encoded = [1,2,3].

You are given the encoded array and an integer first, that is the first element of arr.

Return arr.

• Examples
• Constraints
• Iterative Reconstruction
• Brute Force Search

Examples

Input: encoded = [1,2,3], first = 1
Output: [1,0,2,1]
Explanation: If arr = [1,0,2,1], then first = 1 and encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

Input: encoded = [6,2,7,3], first = 4
Output: [4,2,0,7,4]

Constraints

- 2 <= n <= 10^4
- encoded.length == n - 1
- 0 <= encoded[i] <= 10^5
- 0 <= first <= 10^5

Iterative Reconstruction

Intuition The XOR operation has a unique property: if a ^ b = c, then a ^ c = b. Since we know encoded[i] (which is c) and arr[i] (which is a), we can directly compute arr[i+1] (which is b) by XORing the current element with the corresponding encoded element.

Steps

• Initialize the result array with the first element.
• Iterate through the encoded array.
• For each element, calculate the next value by XORing the current value with the encoded value.
• Append the calculated value to the result array.
• Return the result array.

from typing import List

class Solution:
    def decode(self, encoded: List[int], first: int) -> List[int]:
        arr = [first]
        for x in encoded:
            arr.append(arr[-1] ^ x)
        return arr

Complexity

• Time: O(n)
• Space: O(n) (to store the result)
• Notes: This is the optimal solution, utilizing the mathematical property of XOR to solve the problem in a single pass.

Brute Force Search

Intuition Since the values are constrained to a relatively small range (0 to 10⁵), we can theoretically find the next number by checking every possible integer in that range until we find one that satisfies the XOR condition arr[i] ^ arr[i+1] == encoded[i].

Steps

• Initialize the result array with the first element.
• Iterate through the encoded array.
• For each position, iterate through all possible numbers from 0 to 10⁵.
• Check if current_val ^ candidate == encoded[i].
• If true, append candidate to the result and break the inner loop.
• Return the result array.

from typing import List

class Solution:
    def decode(self, encoded: List[int], first: int) -> List[int]:
        arr = [first]
        for x in encoded:
            current = arr[-1]
            next_val = -1
            for candidate in range(100001):
                if current ^ candidate == x:
                    next_val = candidate
                    break
            arr.append(next_val)
        return arr

Complexity

• Time: O(n * m), where m is the maximum value in the array (10⁵).
• Space: O(n)
• Notes: This approach is significantly slower than the optimal solution and is not recommended for large inputs, but it demonstrates a naive search strategy.