Solution: Decode XORed Permutation

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #1734 (Medium): 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 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.

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:

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 0th 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 0s and 1s:

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:

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:

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:

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