https://leetcode.com/problems/decode-xored-permutation/ from Amazon

Thinking process:

When it comes to XOR, we need to know an important property: a xor b xor b = a, so we can basically cancel a number by XOR it twice. Knowing this property, I tried to XOR all encoded number and thus I got everything canceled except for perm[0] and perm[-1]. This doesn’t really help for finding the final perm.

I got stuck at here for a while. Finally found that I missed one condition: n is always odd. Since XOR always need two numbers, we might be able to get a XOR value which comes from all numbers in perm except for one number?

And, we also know that P0, P1, ..., Pn-1 is a permutation of 1, 2, ..., n, so we can easily get P0 xor P1 xor ... xor Pn-1. As a result, we can use all we just got to xor 1, 2, ..., n so that we can cancel P0, P1, ..., Pn-2 and get excatly Pn-1.

After getting the Pn-1, we can get Pn-2, Pn-3, ..., P0 reversely.

Here is the code.

 1class Solution {
 2public:
 3    vector<int> decode(vector<int>& encoded) {
 4        int N = encoded.size();
 5        int T = N + 1;
 6        int all = 0;
 7        for (int i=0; i<N; i+=2) {
 8            all ^= encoded[i];
 9        }
10        for (int i=1; i<=T; i++) {
11            all ^= i;
12        }
13        vector<int> perm(T);
14        perm[T-1] = all;
15        for (int i=T-2; i>=0; i--) {
16            perm[i] = perm[i+1]^encoded[i];
17        }
18        return perm;
19    }
20};