XOR: LC 1734. Decode XORed Permutation

A super nice XOR problem in today’s biweekly contest.

Problem

1734. Decode XORed Permutation

Idea

For the following example, if we have n as 7, and suppose the perm is

[1, 2, 3, 4, 5, 6, 7]

we will have encoded as

[1 xor 2, 2 xor 3, 3 xor 4, 4 xor 5, 5 xor 6, 6 xor 7]

If we pick up the bolded ones, we will have

2 xor 3 xor 4 xor 5 xor 6 xor 7

So if we do the following operation, we will get 1. (A nice property for XOR operations, if you are not familiar with this, try to verify it by yourself first.)

(2 xor 3 xor 4 xor 5 xor 6 xor 7) xor (1 xor 2 xor 3 xor 4 xor 5 xor 6 xor 7).

Actually, we can replace the number to index of the array and we can get the the first element of the array. If we know the first element of the array, we are done.

Also, from the example, we can see if we set n as an even number, we can not find the first element easily.

Code

int seen[100010];
class Solution {
public:
    vector<int> decode(vector<int>& a) {
        int n = a.size() + 1;
        int first = 0;
        // (2 xor 3 xor 4 xor 5 xor 6 xor 7) in the example
        for (int i = 1; i < n - 1; i += 2) {
            first ^= a[i];
        }
        // (2 xor 3 xor 4 xor 5 xor 6 xor 7) xor (1 xor 2 xor 3 xor 4 xor 5 xor 6 xor 7)
        for (int i = 1; i <= n; ++i){
            first ^= i;
        }
        vector<int> ret(n);
        ret[0] = first;
        for (int i = 1; i < n; ++i) ret[i] = ret[i-1]^a[i-1];
        return ret;
    }
};

Category

XOR