LeetCode: Decode Xored Permutation Solution

Approach

For example, we have original perm:

The encoded (input) would be:

Transform the encoded to

(loop from 1st element of encoded, accumulated xor) (1)

We calculate

(loop from 1 to the perm size, accumulated xor) (2)

From (1) (2), we calculate

by:

Having

, we will now have the perm:

Implementation

1/*
2XOR (^):
3  1 ^ 0 = 1
4  0 ^ 1 = 1
5  1 ^ 1 = 0
6  0 ^ 0 = 0
7
8  0 ^ a = a
9  a ^ a = 0
10*/
11
12var decode = function (encoded) {
13  const a0XorTheRest = [encoded[0]]
14  let acc = encoded[0]
15  for (let i = 1; i < encoded.length; i++) {
16    acc ^= encoded[i]
17    a0XorTheRest.push(acc)
18  }
19  let a0AccXorToAn = 0
20  for (let i = 1; i <= encoded.length + 1; i++) {
21    a0AccXorToAn ^= i
22  }
23  const a1 = a0XorTheRest.reduce((acc, el) => (acc ^= el), 0) ^ a0AccXorToAn
24  const perm = [a1]
25  a0XorTheRest.forEach(el => perm.push(a1 ^ el))
26  return perm
27}