# 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 = 14 0 ^ 1 = 15 1 ^ 1 = 06 0 ^ 0 = 078 0 ^ a = a9 a ^ a = 010*/1112var 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 = 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}

## Comments

Loading comments...

## Tags

leetcode

## Apply and earn a $2,500 bonus once you're hired on your first job!

Clients from the Fortune 500 to Silicon Valley startups

Choose your own rate, get paid on time

From hourly, part-time, to full-time positions

Flexible remote working environment

A lot of open JavaScript jobs!!

**Fact corner:** Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.

**Still hesitate?** Read HoningJS author's guide on dealing with Toptal interview process.

## Next Post

LeetCode: Find The Highest Altitude

Jan 24, 2021

## Previous Post

LeetCode: Minimum Number Of People To Teach

Jan 24, 2021