LeetCode: Decode Xored Permutation Solution

Approach

For example, we have original perm: [a0, a1, a2, a3, a4]

The encoded (input) would be: [a0^a1, a1^a2, a2^a3, a3^a4]

Transform the encoded to [a0^a1, a0^a2, a0^a3, a0^a4] (loop from 1st element of encoded, accumulated xor) (1)

We calculate a0^a1^a2^a3^a4 (loop from 1 to the perm size, accumulated xor) (2)

From (1) (2), we calculate a0 by: (a0^a1) ^ (a0^a2) ^ (a0^a3) ^ (a0^a4) ^ (a0^a1^a2^a3^a4) = a0

Having a0, we will now have the perm: [a0, a0^(a0^a1), a0^(a0^a2), a0^(a0^a3), a0^(a0^a4)] = [a0, a1, a2, a3, a4]

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}