Solution: Decode XORed Permutation
Tags: algorithms, javascript, leetcode
Published: 2021-02-05 23:29:33

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/decode-xored-permutation/discuss/1035374/javascriptpython-simple-5-line-solution-w-explanation-beats-100).*

---

####[Leetcode Problem #1734 (*Medium*): Decode XORed Permutation](https://leetcode.com/problems/decode-xored-permutation/)####

---

***Description:***

*There is an integer array `perm` that is a permutation of the first `n` positive integers, where `n` is always __odd__.*

*It was encoded into another integer array `encoded` of length `n - 1`, such that `encoded[i] = perm[i] XOR perm[i + 1]`. For example, if `perm = [1,3,2]`, then `encoded = [2,1]`.*

*Given the `encoded` array, return the original array `perm`. It is guaranteed that the answer exists and is unique.*

---

***Examples:***

Example 1:||
|---:|---|
*Input:*|encoded = [3,1]
*Output:*|[1,2,3]
*Explanation:*|If perm = [1,2,3], then<br>encoded = [1 XOR 2,2 XOR 3] = [3,1]

Example 2:||
|---:|---|
*Input:*|encoded = [6,5,4,6]
*Output:*|[2,4,1,5,3]

---

***Constraints:***
 - `3 <= n < 10^5`
 - `n` is odd.
 - `encoded.length == n - 1`

---

***Idea:***

The trick to this problem is realizing that a **bitwise XOR ( ^ )** operation is both associative and its own inverse function.
```javascript
if:  a ^ b ^ c = d                    // XOR is associative: the order of operations
 ⇒:  c ^ b ^ a = d                    // for consecutive XOR's does not matter
			  
if:  x ^ y = z                        // XOR is its own inverse function:
 ⇒:  z ^ y = x                        // You can undo the equation from the answer
 ⇒:  x ^ y ^ y = x                    // Two same operations cancel each other out
```
This, plus the fact that the numbers in the encoded array **E** are formed by XOR'ing consecutive elements of **perm**, plus the fact that we know the numbers that make up the whole **perm** array, plus the fact that the length of the **perm** array must be odd, mean that we can easily deduce the first element of **perm**:
```javascript
if:  perm = [ a, b, c, d, e ]             // This is true regardless of the order of
 ⇒:  a^b^c^d^e = 1^2^3^4^5                // #s in perm, b/c XOR is associative
   
if:  E[1] = b^c                           // By the encoding definition
if:  E[3] = d^e
   
 ⇒:  (1^2^3^4^5) ^ E[1] ^ E[3]            // Therefore, if we XOR all #s from
   = (a^b^c^d^e) ^ (b^c) ^ (d^e)          // 1 to N along w/ odd elements of E
   = a ^ (b^b) ^ (c^c) ^ (d^d) ^ (e^e)    // then rearrange terms via association
   = a ^ 0 ^ 0 ^ 0 ^ 0                    // then most of the terms will cancel out
   = a		                              // leaving us with just a, or perm[0]
```
(*Note: Had we used **E[0]** and **E[3]** in the example above, we could have isolated **perm[2]**, or **E[0]** and **E[2]** would yield **perm[4]**; any odd element of **perm** can be deduced this way, as long as the length of **perm** is odd.*)

Conveniently, the XOR of all values between **1** and **N** can be determined mathematically for all odd values of **N**. Because an even number and the odd number that follows only vary in the **0**th bit, when they are XOR'd the rest of the bits will always cancel out, leaving only a **1**. With this, we can see that for all odd values of **N**, this will simplify to alternating **0**s and **1**s:
```javascript
if:  even ^ (even+1) = 1
 ⇒:  1 ^ 2 ^ 3 ^ 4 ^ 5                  ⇒:  1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 
   = 1 ^ (2^3) ^ (4^5)                     = 1 ^ (2^3) ^ (4^5) ^ (6^7)
   = 1 ^ 1 ^ 1                             = 1 ^ 1 ^ 1 ^ 1
   = 1                                     = 0
```
Thus we can simplify the equation for the XOR of all numbers from **1** to **N** for all odd values of **N** to **(N + 1 >> 1) % 2**.

Also, since XOR is its own inverse function, we can work the encoding equation backwards:
```javascript
if:  E[i] = perm[i] ^ perm[i+1]           // By the encoding definition
 ⇒:  perm[i+1] = E[i] ^ perm[i]           // Inverted to solve for perm[i+1]
```
With **perm[0]** and this equation, we can quickly build out the rest of **perm** before returning it.

---

***Javascript Code:***
```javascript
var decode = function(E) {
    let len = E.length, first = (len + 2 >> 1) % 2
    for (let i = 1; i < len; i += 2) first ^= E[i]
    let perm = [first]
    for (let i = 0; i < len; i++) ans[i+1] = ans[i] ^ E[i]
    return perm
};
```

---

***Python Code:***
```python
class Solution(object):
    def decode(self, E):
        L = len(E)
        first = (L + 2 >> 1) % 2
        for i in range(1,L,2):
            first ^= E[i]
        perm = [first]
        for el in E:
            ans.append(perm[-1] ^ el)
        return perm
```