Decode XORed Array

To decode the original array, you can follow these steps:

  1. Initialize the original array arr with its first element first.
  2. Iterate through the encoded array and compute the next elements of arr using the XOR operation with the previous element of arr.
  3. Continue this process to reconstruct the original array.

Here’s a Python code that implements the above logic:

1
2
3
4
5
6

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

Explanation

  • arr[-1] gives the last element of the current arr.
  • XOR (^) is used to decode the next element as encoded[i] = arr[i] XOR arr[i + 1], so you can obtain arr[i + 1] = encoded[i] XOR arr[i].
  • The loop continues this process through the entire encoded array, and finally, arr is returned as the result.

title: Decode XORed Array excerpt: This article demonstrates the building block - Compute Next Value by Manipulating Current Value. tags: bitwise-xor compute-next-value-by-manipulating-current-value

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

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def decode(encoded, first)
  n = encoded.size
  output = Array.new(n + 1)
  output[0] = first
  
  for i in (0..n-1)
    output[i+1] = output[i] ^ encoded[i]
  end
  
  output
end

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

p decode(encoded, first)

Building Blocks

  • Compute Next Value by Manipulating Current Value
  • Bitwise XOR