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.

&nbsp;
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]


&nbsp;
Constraints:


	3 &lt;= n &lt;&nbsp;105
	n&nbsp;is odd.
	encoded.length == n - 1


from functools import reduce
from operator import xor

class Solution:

    def decode(self, encoded: List[int]) -> List[int]:
        n = len(encoded) + 1
        a = reduce(xor, range(1, n+1))
        b = reduce(xor, encoded[1::2])
        result = [a ^ b]
        for y in encoded:
            result.append(result[-1] ^ y)
        return result
class Solution {
    public int[] decode(int[] encoded) {
        int n = encoded.length+1, all = 0;
        for(int i = 1; i <= n; ++i){//a^b^c^d^e^f^g^h^i
            all ^= i;
        }
        int x = 0;
        for(int v : encoded){//a^b  b^c  c^d  d^e e^f f^g g^h h^i = a^i
            x ^= v;
        }
        int mid = all^x; //a^b^c^d^e^f^g^h^i ^ a^i = b^c^d^e^f^g^h
        for(int i = 1, j = encoded.length-2; i < j;i += 2, j -= 2){
        //(b^c^d^e^f^g^h) ^ (b^c ^ g^h ^ d^e ^ e^f) = e
            mid ^= encoded[i]^encoded[j];
        }
        int[] ans = new int[n];
        ans[n/2] = mid;
        //a    b    c    d   e   f   g   h   i
        //a^b  b^c  c^d  d^e e^f f^g g^h h^i
        for(int i = n/2+1; i < n; ++i){
            ans[i] = encoded[i-1]^ans[i-1];
        }
        for(int i = n/2-1; i >= 0; --i){
            ans[i] = encoded[i]^ans[i+1];
        }
        return ans;
    }
}
class Solution {
public:
    vector<int> decode(vector<int>& encoded) {
        int n = encoded.size(), x = 0;
        // XOR of the permutation
        for(int i = 1; i<=n+1; i++) x ^= i;

        // Xoring X with all the odd positioned elements to find first number
        for(int i = 1; i<n; i+=2) x ^= encoded[i];

        vector <int> res;
        res.push_back(x);
        for(int i = 0; i<n; i++){
            x ^= encoded[i];
            res.push_back(x);
        }
        return res;
    }
};
var decode = function(encoded) {
  const n = encoded.length + 1;
  const perm = Array(n);
  for (let i = 1; i <= n; i++) { perm[0] ^= i }
  for (let i = 1; i < n - 1; i += 2) { perm[0] ^= encoded[i] }
  for (let i = 1; i < n; i++) { perm[i] = perm[i - 1] ^ encoded[i - 1] }
  return perm;
};
Decode XORed Permutation