Decode XORed Array

You are given an encoded array where encoded[i] = arr[i] XOR arr[i + 1] and the first element of arr is also given. Reconstruct the original array. Pattern focus: XOR State Tracking. Recover each next value by XORing the current prefix state with the encoded value.

Input Format

encoded = XOR differences, first = first element of the original array

Output Format

the reconstructed original array

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • encoded, first must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

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

Output:

[1,0,2,1]

Explanation:

Each next value is obtained by XORing the current value with the next encoded entry.

Example 2:

Input:

encoded = [6,2,7,3]
first = 4

Output:

[4,2,0,7,4]

Explanation:

The XOR chain is followed step by step.

Loading...
Decode XORed Array - Bit Manipulation