Decode XORed Permutation

You are given an encoded array of a permutation perm of the first n positive integers, where encoded[i] = perm[i] XOR perm[i + 1]. Reconstruct the permutation. Pattern focus: XOR State Tracking. Use the XOR of 1..n and the XOR of odd-positioned encoded values to recover the first element, then rebuild the rest.

Input Format

encoded = XOR-encoded permutation

Output Format

the original permutation

Constraints

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

Examples

Example 1:

Input:

encoded = [3,1]

Output:

[1,2,3]

Explanation:

The permutation 1,2,3 produces encoded values 3 and 1.

Example 2:

Input:

encoded = [6,5,4,6]

Output:

[2,4,1,5,3]

Explanation:

The original permutation is reconstructed from the XOR state.

Loading...
Decode XORed Permutation - Bit Manipulation