{x}
blog image

Decode XORed Array

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.

 

Example 1:

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:

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

 

Constraints:

  • 2 <= n <= 104
  • encoded.length == n - 1
  • 0 <= encoded[i] <= 105
  • 0 <= first <= 105

Solution Explanation: Decoding XORed Array

This problem involves decoding an array that's been encoded using XOR operations. The core idea is to leverage the properties of XOR to recover the original array.

Understanding the XOR Encoding:

The input encoded array is created by XORing consecutive elements of the original array arr. That is:

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

We're given first, which is the value of arr[0]. The goal is to reconstruct the entire arr array.

The Solution:

The key insight is that XOR is its own inverse. That is, x XOR x = 0, and x XOR 0 = x.

Let's examine how to recover arr[1] :

We know encoded[0] = arr[0] XOR arr[1]. Since we know arr[0] (first), we can solve for arr[1] as follows:

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

We can generalize this approach to recover any arr[i] :

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

Algorithm:

  1. Initialize: Create a new array ans and initialize it with first (the value of arr[0]).
  2. Iterate: Loop through the encoded array. For each element encoded[i]:
    • Calculate the next element of arr using the formula: ans[i+1] = ans[i] XOR encoded[i]
    • Append the calculated ans[i+1] to the ans array.
  3. Return: Return the ans array, which now contains the reconstructed original array.

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the encoded array. We iterate through the encoded array once.
  • Space Complexity: O(n). We create a new array ans of size n+1 to store the reconstructed array.

Code Examples:

The code implementations provided in Python, Java, C++, Go and TypeScript all follow this algorithm. They differ only in syntax and specific language features, but the underlying logic remains consistent. Each example demonstrates a concise and efficient implementation of the solution.

Example Walkthrough (Python):

Let's trace the Python code with encoded = [1, 2, 3] and first = 1:

  1. ans is initialized to [1].
  2. Loop begins:
    • ans[1] = ans[0] ^ encoded[0] = 1 ^ 1 = 0. ans becomes [1, 0].
    • ans[2] = ans[1] ^ encoded[1] = 0 ^ 2 = 2. ans becomes [1, 0, 2].
    • ans[3] = ans[2] ^ encoded[2] = 2 ^ 3 = 1. ans becomes [1, 0, 2, 1].
  3. The function returns [1, 0, 2, 1], which is the correctly decoded array.

The other languages' implementations work identically. They just use their own respective syntax and data structures.