LeetCode 1720 - Decode XORed Array

The problem gives us an encoded array where each element represents the XOR of two consecutive elements from an unknown original array. Specifically: We are also given the first element of the original array, first = arr[0].

leetcodeeasyarraybit-manipulation

LeetCode Problem 1720

Difficulty: 🟢 Easy
Topics: Array, Bit Manipulation

Solution

Problem Understanding

The problem gives us an encoded array where each element represents the XOR of two consecutive elements from an unknown original array. Specifically:

encoded[i] = arr[i] XOR arr[i + 1]

We are also given the first element of the original array, first = arr[0]. Using these two pieces of information, we must reconstruct the entire original array.

The key observation is that XOR has reversible properties. If:

a XOR b = c

then:

a XOR c = b

This means that if we already know one value in the original array and the XOR result between it and the next value, we can recover the next value directly.

For example, suppose:

encoded = [1,2,3]
first = 1

We know:

arr[0] = 1
encoded[0] = arr[0] XOR arr[1] = 1

So:

arr[1] = arr[0] XOR encoded[0]
       = 1 XOR 1
       = 0

Then we continue:

arr[2] = arr[1] XOR encoded[1]
       = 0 XOR 2
       = 2

and so on.

The constraints are relatively small:

  • 2 <= n <= 10^4
  • 0 <= encoded[i], first <= 10^5

This tells us that even an O(n) solution is more than fast enough. The problem is primarily about understanding XOR behavior correctly rather than optimizing for massive input sizes.

An important guarantee is that the answer always exists and is unique. This means there is exactly one valid original array corresponding to the provided input.

Some edge cases that could cause mistakes include:

  • Arrays of minimum size, where encoded contains only one value.
  • Values equal to zero, since XOR with zero leaves values unchanged.
  • Repeated numbers, which can produce encoded values of zero.
  • Forgetting that the output array has length encoded.length + 1.

Approaches

Brute Force Approach

A naive brute force approach would try to guess every possible value of the original array and check whether it produces the given encoded array.

For each adjacent pair:

arr[i] XOR arr[i + 1] == encoded[i]

we would validate whether the guessed array satisfies all constraints.

This approach is technically correct because it explores all possibilities, but it is completely impractical. Each array element can be as large as 10^5, which creates an enormous search space. Even for small inputs, exhaustive search would become infeasible.

The brute force method demonstrates correctness conceptually, but it ignores the reversible nature of XOR.

Optimal Approach

The optimal solution relies on a fundamental XOR property:

a XOR b = c

implies:

b = a XOR c

Since the first element of the array is already known, we can reconstruct the remaining elements one by one.

If:

encoded[i] = arr[i] XOR arr[i + 1]

then:

arr[i + 1] = arr[i] XOR encoded[i]

This allows us to build the array sequentially in a single pass.

Because each element is computed exactly once, the algorithm runs in linear time.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential O(n) Tries all possible arrays and validates them
Optimal O(n) O(n) Reconstructs the array directly using XOR properties

Algorithm Walkthrough

  1. Create the result array and place first as the first element.

We already know the value of arr[0], so the reconstruction starts with this guaranteed value. 2. Iterate through each value in encoded.

Each encoded value represents the XOR of two adjacent elements in the original array. 3. Recover the next element using XOR reversal.

Since:

encoded[i] = arr[i] XOR arr[i + 1]

we compute:

arr[i + 1] = arr[i] XOR encoded[i]

This works because XOR cancels identical values. 4. Append the recovered value to the result array.

Each new value becomes the basis for computing the next one. 5. Continue until all encoded values are processed.

Since encoded has length n - 1, the reconstructed array will contain exactly n elements. 6. Return the completed array.

Why it works

The algorithm works because XOR is reversible. For every adjacent pair:

encoded[i] = arr[i] XOR arr[i + 1]

If we already know arr[i], then XORing it again with encoded[i] removes it and reveals arr[i + 1].

This property guarantees that every next value is reconstructed correctly and uniquely.

Python Solution

from typing import List

class Solution:
    def decode(self, encoded: List[int], first: int) -> List[int]:
        result = [first]

        for value in encoded:
            next_number = result[-1] ^ value
            result.append(next_number)

        return result

The implementation begins by initializing the result array with the known first value.

The loop processes each value in encoded. At every iteration, the previous decoded number is retrieved using result[-1].

Using the XOR property:

arr[i + 1] = arr[i] XOR encoded[i]

the next original value is computed and appended to the result array.

After processing all encoded values, the reconstructed array is returned.

Go Solution

func decode(encoded []int, first int) []int {
    result := make([]int, 1, len(encoded)+1)
    result[0] = first

    for _, value := range encoded {
        nextNumber := result[len(result)-1] ^ value
        result = append(result, nextNumber)
    }

    return result
}

The Go solution follows the same logic as the Python version.

A slice is initialized with capacity len(encoded) + 1 to avoid repeated reallocations during appends.

Go integers are fully sufficient for the given constraints, so there are no overflow concerns here.

Unlike Python lists, Go slices require explicit initialization with make.

Worked Examples

Example 1

Input:

encoded = [1,2,3]
first = 1

Initial state:

result = [1]
Step Encoded Value Previous Value Computation Result
1 1 1 1 XOR 1 = 0 [1,0]
2 2 0 0 XOR 2 = 2 [1,0,2]
3 3 2 2 XOR 3 = 1 [1,0,2,1]

Final output:

[1,0,2,1]

Example 2

Input:

encoded = [6,2,7,3]
first = 4

Initial state:

result = [4]
Step Encoded Value Previous Value Computation Result
1 6 4 4 XOR 6 = 2 [4,2]
2 2 2 2 XOR 2 = 0 [4,2,0]
3 7 0 0 XOR 7 = 7 [4,2,0,7]
4 3 7 7 XOR 3 = 4 [4,2,0,7,4]

Final output:

[4,2,0,7,4]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each encoded element is processed exactly once
Space O(n) The reconstructed array stores n elements

The algorithm performs a single linear traversal of the encoded array. Every iteration does constant work using XOR operations and appending to the result list.

The extra space comes from storing the decoded array itself. No additional auxiliary data structures are required.

Test Cases

from typing import List

class Solution:
    def decode(self, encoded: List[int], first: int) -> List[int]:
        result = [first]

        for value in encoded:
            result.append(result[-1] ^ value)

        return result

solution = Solution()

# Provided example 1
assert solution.decode([1, 2, 3], 1) == [1, 0, 2, 1]

# Provided example 2
assert solution.decode([6, 2, 7, 3], 4) == [4, 2, 0, 7, 4]

# Minimum valid input size
assert solution.decode([5], 2) == [2, 7]

# All zeros
assert solution.decode([0, 0, 0], 0) == [0, 0, 0, 0]

# Repeated values in original array
assert solution.decode([0, 0, 0], 9) == [9, 9, 9, 9]

# Alternating pattern
assert solution.decode([1, 1, 1, 1], 0) == [0, 1, 0, 1, 0]

# Larger values
assert solution.decode([100000, 99999], 12345) == [
    12345,
    12345 ^ 100000,
    (12345 ^ 100000) ^ 99999,
]

# Single transition to zero
assert solution.decode([7], 7) == [7, 0]

# Single transition from zero
assert solution.decode([7], 0) == [0, 7]
Test Why
[1,2,3], first=1 Validates the first official example
[6,2,7,3], first=4 Validates the second official example
Single encoded element Tests minimum input size
All zeros Ensures XOR with zero is handled correctly
Repeated original values Confirms identical adjacent numbers produce encoded zero
Alternating values Tests repeated XOR transitions
Large numbers Verifies correctness near constraint limits
Transition to zero Ensures XOR cancellation works
Transition from zero Ensures zero starting values work correctly

Edge Cases

One important edge case is the minimum valid input size. Since encoded.length = n - 1, the smallest possible encoded array contains only one element. A buggy implementation might accidentally assume multiple iterations or mishandle indexing. The current implementation handles this naturally because the loop simply runs once and appends a single recovered value.

Another important case involves zeros. XOR has the identity property:

x XOR 0 = x

and also:

x XOR x = 0

Arrays with repeated values therefore produce encoded values of zero. Some implementations incorrectly treat zero as a special invalid case, but the algorithm works uniformly regardless of whether encoded values are zero.

A third edge case is large values near the upper constraint limit. Since XOR is a bitwise operation and does not grow values beyond integer storage capacity for these constraints, the algorithm remains efficient and safe. Both Python and Go handle the required integer range comfortably.

A subtle implementation issue is ensuring the output array has length encoded.length + 1. Since every encoded value corresponds to a transition between two original elements, forgetting to include the initial first value would produce an array that is too short. Initializing the result with first guarantees the correct final size.