Decode XORed Array
To decode the original array, you can follow these steps:
- Initialize the original array
arr
with its first elementfirst
. - Iterate through the
encoded
array and compute the next elements ofarr
using the XOR operation with the previous element ofarr
. - Continue this process to reconstruct the original array.
Here’s a Python code that implements the above logic:
|
|
Explanation
arr[-1]
gives the last element of the currentarr
.- XOR (
^
) is used to decode the next element asencoded[i] = arr[i] XOR arr[i + 1]
, so you can obtainarr[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
|
|
Building Blocks
- Compute Next Value by Manipulating Current Value
- Bitwise XOR