# Decode XORed Permutation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/decode-xored-permutation)
Canonical: https://scaleengineer.com/dsa/problems/decode-xored-permutation
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
---
## Problem
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 < 105`
* `n` is odd.
* `encoded.length == n - 1`

# Approaches
## Brute Force by Trying All Possible First Elements
This approach involves iterating through all possible values for the first element of the permutation, which must be a number from `1` to `n`. For each guess, we reconstruct the entire permutation array using the given `encoded` array. We then check if the reconstructed array is a valid permutation (i.e., contains each number from `1` to `n` exactly once). Since the solution is guaranteed to be unique, the first valid permutation we find is the answer.
**Time:** O(n^2), where `n` is the size of the permutation array. The outer loop runs `n` times. For each iteration, we generate a new permutation (O(n)) and then validate it (O(n) using a HashSet). This results in a total complexity of O(n * (n + n)) = O(n^2). · **Space:** O(n) to store the candidate `perm` array and the `HashSet` used for validation.
**Pros:** Conceptually simple and straightforward to implement.
**Cons:** Inefficient for large values of `n`. Given the constraint `n < 10^5`, this approach will be too slow and result in a 'Time Limit Exceeded' error.
### Explanation
The core of this method is trial and error. We know `perm[0]` has to be one of the integers in `[1, 2, ..., n]`. We can systematically try each of these `n` possibilities.
For a given guess `p0` for `perm[0]`, we can derive the rest of the `perm` array using the relationship `perm[i] = perm[i-1] XOR encoded[i-1]`. After constructing a full candidate `perm` array, we must validate it. A valid `perm` array must be a permutation of `[1, 2, ..., n]`, meaning it contains each of these numbers exactly once and no other numbers. We can use a `HashSet` or a frequency array to check for duplicates and ensure all numbers are within the valid range `[1, n]`. The first guess for `perm[0]` that results in a valid permutation gives us our final answer.
```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] decode(int[] encoded) {
        int n = encoded.length + 1;
        int[] perm = new int[n];

        // Iterate through all possible values for the first element
        for (int first = 1; first <= n; first++) {
            perm[0] = first;
            
            // Generate the rest of the permutation
            for (int i = 0; i < n - 1; i++) {
                perm[i + 1] = perm[i] ^ encoded[i];
            }

            // Validate the generated permutation
            if (isValidPermutation(perm, n)) {
                return perm;
            }
        }
        
        return new int[0]; // Should not be reached as a solution is guaranteed
    }

    private boolean isValidPermutation(int[] perm, int n) {
        Set<Integer> seen = new HashSet<>();
        for (int num : perm) {
            if (num < 1 || num > n || !seen.add(num)) {
                return false; // Invalid number or duplicate found
            }
        }
        return seen.size() == n;
    }
}
```
### Algorithm
- Determine the size of the permutation, `n = encoded.length + 1`.
- Iterate through each integer `p0` from `1` to `n` as a potential candidate for `perm[0]`.
- For each `p0`:
    - Create a candidate array `perm` of size `n` and set `perm[0] = p0`.
    - Calculate the remaining elements of `perm` using the formula: `perm[i] = perm[i-1] XOR encoded[i-1]` for `i` from `1` to `n-1`.
    - Check if the generated `perm` is a valid permutation of `1` to `n`. This can be done by using a `HashSet` to track seen numbers and ensure there are no duplicates and all numbers are within the range `[1, n]`.
    - If the `perm` is valid, return it as the answer.

## Finding the First Element using XOR Properties
This optimal approach cleverly uses the properties of the XOR operation to determine the first element of the permutation, `perm[0]`, directly. By finding `perm[0]`, the rest of the array can be decoded in a single pass. This avoids the trial-and-error of the brute-force method.
**Time:** O(n), where `n` is the size of the permutation. Calculating `total_xor` takes O(n), calculating `odd_indices_xor` takes O(n), and reconstructing the final `perm` array takes O(n). The overall complexity is linear. · **Space:** O(n) to store the output `perm` array. If the output array is not considered part of the space complexity, the algorithm uses O(1) extra space.
**Pros:** Highly efficient with linear time complexity, making it suitable for large inputs.; Guaranteed to find the unique solution directly without searching.
**Cons:** The logic relies on a non-obvious mathematical property of the XOR operation, which can be difficult to derive during an interview.
### Explanation
The key insight is to relate the XOR sum of all elements in the permutation to the XOR sum of elements in the `encoded` array.
1.  **Total XOR Sum:** Since `perm` is a permutation of `1, 2, ..., n`, the XOR sum of all its elements is known: `total_xor = 1 XOR 2 XOR ... XOR n`.
2.  **Relating to `encoded`:** The `encoded` array is defined as `encoded[i] = perm[i] XOR perm[i+1]`. Let's consider the XOR sum of elements of `encoded` at odd indices: `encoded[1] XOR encoded[3] XOR ... XOR encoded[n-2]`. (Note: `n` is odd, so `n-2` is also odd).
    This sum expands to: `(perm[1] XOR perm[2]) XOR (perm[3] XOR perm[4]) XOR ... XOR (perm[n-2] XOR perm[n-1])`.
    Due to the associative property of XOR, this simplifies to `perm[1] XOR perm[2] XOR ... XOR perm[n-1]`. This is the XOR sum of all elements in `perm` *except* `perm[0]`.
3.  **Finding `perm[0]`:** We have two equations:
    - `total_xor = perm[0] XOR perm[1] XOR ... XOR perm[n-1]`
    - `odd_indices_xor = perm[1] XOR perm[2] XOR ... XOR perm[n-1]`
    If we XOR these two values together:
    `total_xor XOR odd_indices_xor = (perm[0] XOR ... XOR perm[n-1]) XOR (perm[1] XOR ... XOR perm[n-1])`
    The terms `perm[1]` through `perm[n-1]` appear twice and cancel out (since `x XOR x = 0`), leaving only `perm[0]`.
    Thus, `perm[0] = total_xor XOR odd_indices_xor`.
Once we calculate `perm[0]`, we can find the rest of the elements sequentially: `perm[i] = perm[i-1] XOR encoded[i-1]`.
```java
class Solution {
    public int[] decode(int[] encoded) {
        int n = encoded.length + 1;
        int[] perm = new int[n];

        // 1. Calculate the XOR sum of the permutation (1 XOR 2 XOR ... XOR n)
        int total_xor = 0;
        for (int i = 1; i <= n; i++) {
            total_xor ^= i;
        }

        // 2. Calculate the XOR sum of elements at odd indices in 'encoded'
        // This gives us perm[1] ^ perm[2] ^ ... ^ perm[n-1]
        int odd_indices_xor = 0;
        for (int i = 1; i < encoded.length; i += 2) {
            odd_indices_xor ^= encoded[i];
        }

        // 3. Find the first element of the permutation
        // perm[0] = total_xor ^ odd_indices_xor
        perm[0] = total_xor ^ odd_indices_xor;

        // 4. Reconstruct the rest of the permutation
        for (int i = 0; i < n - 1; i++) {
            perm[i + 1] = perm[i] ^ encoded[i];
        }

        return perm;
    }
}
```
### Algorithm
- Determine the size of the permutation, `n = encoded.length + 1`.
- Calculate `total_xor`, the XOR sum of all integers from `1` to `n`.
- Calculate `odd_indices_xor`, the XOR sum of all elements in the `encoded` array that are at odd indices (`encoded[1]`, `encoded[3]`, etc.).
- Determine the first element of the permutation, `perm[0]`, by XORing the two results: `perm[0] = total_xor XOR odd_indices_xor`.
- Create the result array `perm` of size `n` and place `perm[0]` at the first position.
- Iterate from `i = 0` to `n-2` and compute the subsequent elements: `perm[i+1] = perm[i] XOR encoded[i]`.
- Return the fully constructed `perm` array.

# Solutions
### Java

```java
class Solution { public int [] decode ( int [] encoded ) { int n = encoded . length + 1 ; int a = 0 , b = 0 ; for ( int i = 0 ; i < n - 1 ; i += 2 ) { a ^= encoded [ i ]; } for ( int i = 1 ; i <= n ; ++ i ) { b ^= i ; } int [] perm = new int [ n ]; perm [ n - 1 ] = a ^ b ; for ( int i = n - 2 ; i >= 0 ; -- i ) { perm [ i ] = encoded [ i ] ^ perm [ i + 1 ]; } return perm ; } }
```

### CPP

```cpp
class Solution { public: vector < int > decode ( vector < int >& encoded ) { int n = encoded . size () + 1 ; int a = 0 , b = 0 ; for ( int i = 0 ; i < n - 1 ; i += 2 ) { a ^= encoded [ i ]; } for ( int i = 1 ; i <= n ; ++ i ) { b ^= i ; } vector < int > perm ( n ); perm [ n - 1 ] = a ^ b ; for ( int i = n - 2 ; ~ i ; -- i ) { perm [ i ] = encoded [ i ] ^ perm [ i + 1 ]; } return perm ; } };
```

### Python

```python
class Solution : def decode ( self , encoded : List [ int ]) -> List [ int ]: n = len ( encoded ) + 1 a = b = 0 for i in range ( 0 , n - 1 , 2 ): a ^= encoded [ i ] for i in range ( 1 , n + 1 ): b ^= i perm = [ 0 ] * n perm [ - 1 ] = a ^ b for i in range ( n - 2 , - 1 , - 1 ): perm [ i ] = encoded [ i ] ^ perm [ i + 1 ] return perm
```