Code Implementation

class Solution:
    def decode(self, encoded, first):
        n = len(encoded)
        arr = [first]
        for i in range(n):
            arr.append(arr[-1] ^ encoded[i])
        return arr
      

class Solution {
public:
    vector<int> decode(vector<int>& encoded, int first) {
        vector<int> arr;
        arr.push_back(first);
        for (int i = 0; i < encoded.size(); ++i) {
            arr.push_back(arr.back() ^ encoded[i]);
        }
        return arr;
    }
};
      

class Solution {
    public int[] decode(int[] encoded, int first) {
        int n = encoded.length;
        int[] arr = new int[n + 1];
        arr[0] = first;
        for (int i = 0; i < n; i++) {
            arr[i + 1] = arr[i] ^ encoded[i];
        }
        return arr;
    }
}
      

var decode = function(encoded, first) {
    let arr = [first];
    for (let i = 0; i < encoded.length; i++) {
        arr.push(arr[arr.length - 1] ^ encoded[i]);
    }
    return arr;
};
      

Problem Description

You are given an integer array encoded where the original array arr has been transformed such that encoded[i] = arr[i] XOR arr[i+1] for every valid index i. You are also given the first element of the original array as first.

Your task is to reconstruct and return the original array arr from the encoded array and the given first value.

• Each value in encoded and first is an integer.
• There is exactly one valid solution.
• Do not reuse elements from encoded directly; reconstruct the original array.

Thought Process

At first glance, the problem seems tricky because we only have the XOR of consecutive elements, not the elements themselves. A brute-force approach might involve guessing values, but the presence of the first element gives us a starting point.

The key insight is understanding the properties of the XOR operation:

• XOR is reversible: a XOR b = c implies c XOR a = b and c XOR b = a.
• Given arr[i] and encoded[i], we can compute arr[i+1] as arr[i] XOR encoded[i].

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Initialize a new array arr and set arr[0] = first.
2. Iterate through each element in the encoded array:
   • For each i, calculate arr[i+1] = arr[i] XOR encoded[i].
   • Append the result to arr.
3. Continue this process until all elements are decoded.
4. Return the reconstructed arr.

This approach is efficient because it leverages the reversibility of XOR and only requires a single pass through the encoded array.

Example Walkthrough

Let's work through an example:

Suppose encoded = [6, 2, 7, 3] and first = 4.

• Start with arr = [4].
• Step 1: arr[1] = arr[0] XOR encoded[0] = 4 XOR 6 = 2 ⇒ arr = [4, 2]
• Step 2: arr[2] = arr[1] XOR encoded[1] = 2 XOR 2 = 0 ⇒ arr = [4, 2, 0]
• Step 3: arr[3] = arr[2] XOR encoded[2] = 0 XOR 7 = 7 ⇒ arr = [4, 2, 0, 7]
• Step 4: arr[4] = arr[3] XOR encoded[3] = 7 XOR 3 = 4 ⇒ arr = [4, 2, 0, 7, 4]

The final decoded array is [4, 2, 0, 7, 4].

Time and Space Complexity

Brute-force Approach:

• If we tried all possible arrays, the complexity would be exponential, making it infeasible.

• Time Complexity: O(n), where n is the length of the encoded array. We only loop through the array once.
• Space Complexity: O(n), since we construct a new array arr of size n+1.

The optimization is possible because each step depends only on the previous value and the current encoded value.

Summary

The problem leverages the reversible property of the XOR operation to decode the original array from its encoded form. By sequentially applying XOR using the known first value, we reconstruct the entire array efficiently in linear time. The elegance of the solution lies in recognizing the symmetry of XOR and using it to invert the encoding process with minimal code and optimal performance.