# 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

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}/*2XOR (^):3  1 ^ 0 = 14  0 ^ 1 = 15  1 ^ 1 = 06  0 ^ 0 = 07
8  0 ^ a = a9  a ^ a = 010*/11
12var decode = function (encoded) {13  const a0XorTheRest = [encoded]14  let acc = encoded15  for (let i = 1; i < encoded.length; i++) {16    acc ^= encoded[i]17    a0XorTheRest.push(acc)18  }19  let a0AccXorToAn = 020  for (let i = 1; i <= encoded.length + 1; i++) {21    a0AccXorToAn ^= i22  }23  const a1 = a0XorTheRest.reduce((acc, el) => (acc ^= el), 0) ^ a0AccXorToAn24  const perm = [a1]25  a0XorTheRest.forEach(el => perm.push(a1 ^ el))26  return perm27}```

leetcode

## Next Post

LeetCode: Find The Highest Altitude

Jan 24, 2021

Search Posts