{x}
blog image

Decode XORed Permutation

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.

 

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 < 105
  • n is odd.
  • encoded.length == n - 1

Solution Explanation for Decode XORed Permutation

This problem involves decoding a permutation array perm from its XOR-encoded version encoded. The encoding process is such that encoded[i] = perm[i] XOR perm[i+1]. The key insight lies in leveraging the properties of XOR operations to recover the original permutation.

Core Idea:

  1. XOR Sum of Permutation: The XOR sum of all numbers from 1 to n (where n is odd) is predictable. This is because XOR operations cancel out pairs with the same value. The XOR sum will always be the remaining unpaired number. If we denote this XOR sum as total_xor, then we can write total_xor = 1 ^ 2 ^ ... ^ n. This value can be easily calculated iteratively.

  2. XOR Sum of Encoded Array: The XOR of elements in the encoded array (taking every other element) is related to the original permutation.

  3. Recovering the Last Element: By cleverly combining the XOR sums, we can find the last element of the original perm array. Let's denote the XOR sum of encoded[0], encoded[2], encoded[4],... as encoded_xor_odd. Then, perm[n-1] can be determined as total_xor ^ encoded_xor_odd.

  4. Iterative Decoding: Once we have the last element of perm, we can iteratively reconstruct the entire perm array using the given encoded array and the XOR property: perm[i] = encoded[i] ^ perm[i+1].

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the encoded array. This is because we iterate through the array a constant number of times (once to calculate XOR sums, and once to reconstruct perm).

  • Space Complexity: O(1) extra space, excluding the space used to store the result perm array. We only use a few extra variables to store XOR sums.

Code Implementation (Python):

class Solution:
    def decode(self, encoded: List[int]) -> List[int]:
        n = len(encoded) + 1
        total_xor = 0
        for i in range(1, n + 1):
            total_xor ^= i  # Calculate the XOR sum of 1 to n
 
        encoded_xor_odd = 0
        for i in range(0, n - 1, 2): # XOR sum of encoded[0], encoded[2], ...
            encoded_xor_odd ^= encoded[i]
 
        perm = [0] * n
        perm[n - 1] = total_xor ^ encoded_xor_odd  #Find the last element
 
        for i in range(n - 2, -1, -1):
            perm[i] = encoded[i] ^ perm[i + 1]  #Iteratively decode
 
        return perm

The code in other languages (Java, C++, Go) follows the same logic, differing only in syntax and data structures. The core algorithm remains consistent across all implementations.