Problem

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. You are also given an integer first, that is the first element of arr, i.e. arr[0].

Return the original array arr. It can be proved that the answer exists and is unique.

Examples

Example 1

1
2
3

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]

Example 2

1
2

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

Solution

Method 1 – Prefix XOR Reconstruction

Intuition

Given the first element and the encoded array, we can reconstruct the original array by reversing the XOR operation. Since encoded[i] = arr[i] XOR arr[i+1], we can get arr[i+1] = encoded[i] XOR arr[i].

Approach

  1. Initialize the answer array with the first element.
  2. For each value in the encoded array:
    • Compute the next element as the XOR of the last element in the answer and the current encoded value.
    • Append it to the answer array.
  3. Return the answer array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    vector<int> decode(vector<int>& encoded, int first) {
        int n = encoded.size();
        vector<int> ans(n + 1);
        ans[0] = first;
        for (int i = 0; i < n; ++i) {
            ans[i + 1] = ans[i] ^ encoded[i];
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9

func decode(encoded []int, first int) []int {
    n := len(encoded)
    ans := make([]int, n+1)
    ans[0] = first
    for i := 0; i < n; i++ {
        ans[i+1] = ans[i] ^ encoded[i]
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int[] decode(int[] encoded, int first) {
        int n = encoded.length;
        int[] ans = new int[n + 1];
        ans[0] = first;
        for (int i = 0; i < n; i++) {
            ans[i + 1] = ans[i] ^ encoded[i];
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun decode(encoded: IntArray, first: Int): IntArray {
        val n = encoded.size
        val ans = IntArray(n + 1)
        ans[0] = first
        for (i in 0 until n) {
            ans[i + 1] = ans[i] xor encoded[i]
        }
        return ans
    }
}
1
2
3
4
5
6
7

class Solution:
    def decode(self, encoded: list[int], first: int) -> list[int]:
        n: int = len(encoded)
        ans: list[int] = [first]
        for e in encoded:
            ans.append(ans[-1] ^ e)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn decode(encoded: Vec<i32>, first: i32) -> Vec<i32> {
        let n = encoded.len();
        let mut ans = Vec::with_capacity(n + 1);
        ans.push(first);
        for &e in &encoded {
            let last = *ans.last().unwrap();
            ans.push(last ^ e);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    decode(encoded: number[], first: number): number[] {
        const n = encoded.length;
        const ans = [first];
        for (let i = 0; i < n; i++) {
            ans.push(ans[i] ^ encoded[i]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the encoded array, since we process each element once.
  • 🧺 Space complexity: O(n), for the answer array of size n+1.