Formatted question description: https://leetcode.ca/all/1734.html

# 1734. Decode XORed Permutation

## Level

Medium

## Description

There is an integer array `perm`

that is a permutation of the first `n`

positive integers, where `n`

is always **odd**.

It was encoded into another integer array `encoded`

of length `n - 1`

, such that `encoded[i] = perm[i] XOR perm[i + 1]`

. For example, if `perm = [1,3,2]`

, then `encoded = [2,1]`

.

Given the `encoded`

array, return *the original array perm*. It is guaranteed that the answer exists and is unique.

**Example 1:**

**Input:** encoded = [3,1]

**Output:** [1,2,3]

**Explanation:** If perm = [1,2,3], then encoded = [1 XOR 2,2 XOR 3] = [3,1]

**Example 2:**

**Input:** encoded = [6,5,4,6]

**Output:** [2,4,1,5,3]

**Constraints:**

`3 <= n < 10^5`

`n`

is odd.`encoded.length == n - 1`

## Solution

Use the condition that `n`

is odd to solve this problem. First calculate `totalXOR`

as the XOR from 1 to `n`

. Next, calculate the XOR result of even indices of `encoded`

as `evenXOR`

, and the XOR result of odd indices of `encoded`

as `oddXOR`

. Then there is `decoded[0] = totalXOR ^ oddXOR`

and `decoded[n - 1] = totalXOR ^ evenXOR`

. Finally, for `i`

from 0 to `n - 2`

, there is `decoded[i + 1] = decoded[i] ^ encoded[i]`

.

```
class Solution {
public int[] decode(int[] encoded) {
int length = encoded.length;
int n = length + 1;
int totalXOR = 0;
for (int i = 1; i <= n; i++)
totalXOR ^= i;
int[] decoded = new int[n];
int evenXOR = 0, oddXOR = 0;
for (int i = 0; i < length; i++) {
if (i % 2 == 0)
evenXOR ^= encoded[i];
else
oddXOR ^= encoded[i];
}
decoded[0] = totalXOR ^ oddXOR;
decoded[n - 1] = totalXOR ^ evenXOR;
for (int i = 0; i < length; i++)
decoded[i + 1] = decoded[i] ^ encoded[i];
return decoded;
}
}
```