Code Implementation

class Solution:
    def decode(self, encoded):
        n = len(encoded) + 1
        total = 0
        for i in range(1, n + 1):
            total ^= i

        odd = 0
        for i in range(1, len(encoded), 2):
            odd ^= encoded[i]

        perm = [0] * n
        perm[0] = total ^ odd
        for i in range(len(encoded)):
            perm[i + 1] = perm[i] ^ encoded[i]
        return perm
      

class Solution {
public:
    vector<int> decode(vector<int>& encoded) {
        int n = encoded.size() + 1;
        int total = 0;
        for (int i = 1; i <= n; ++i)
            total ^= i;
        int odd = 0;
        for (int i = 1; i < encoded.size(); i += 2)
            odd ^= encoded[i];
        vector<int> perm(n);
        perm[0] = total ^ odd;
        for (int i = 0; i < encoded.size(); ++i)
            perm[i + 1] = perm[i] ^ encoded[i];
        return perm;
    }
};
      

class Solution {
    public int[] decode(int[] encoded) {
        int n = encoded.length + 1;
        int total = 0;
        for (int i = 1; i <= n; ++i)
            total ^= i;
        int odd = 0;
        for (int i = 1; i < encoded.length; i += 2)
            odd ^= encoded[i];
        int[] perm = new int[n];
        perm[0] = total ^ odd;
        for (int i = 0; i < encoded.length; ++i)
            perm[i + 1] = perm[i] ^ encoded[i];
        return perm;
    }
}
      

var decode = function(encoded) {
    const n = encoded.length + 1;
    let total = 0;
    for (let i = 1; i <= n; ++i)
        total ^= i;
    let odd = 0;
    for (let i = 1; i < encoded.length; i += 2)
        odd ^= encoded[i];
    const perm = new Array(n);
    perm[0] = total ^ odd;
    for (let i = 0; i < encoded.length; ++i)
        perm[i + 1] = perm[i] ^ encoded[i];
    return perm;
};
      

Problem Description

You are given an integer array encoded of length n - 1, where n is always odd and represents the length of a permutation perm of the first n positive integers. The encoded array is constructed such that encoded[i] = perm[i] XOR perm[i + 1] for each i from 0 to n - 2.

Your task is to reconstruct and return the original permutation perm. The constraints guarantee that there is exactly one valid solution, and you must not reuse elements (each integer from 1 to n appears exactly once).

Thought Process

At first glance, this seems challenging because we only know the XOR of adjacent elements, not the elements themselves. A brute-force approach would try all possible permutations, check which one fits the encoded array, and return it. However, this would be extremely slow for larger arrays.

The key insight is that XOR has useful properties: it's reversible (A XOR B XOR B = A), and the order doesn't matter (it's commutative and associative). If we can find one element of perm, we can use the encoded array to reconstruct the rest. But how do we find the first element?

By thinking about the total XOR of all numbers from 1 to n and the pattern of the encoded array, we can deduce the first element and use it to generate the entire permutation efficiently.

Solution Approach

• Step 1: Compute total XOR of all numbers from 1 to n.
  Since perm is a permutation of 1 to n, if we XOR all these numbers together, we get a value total.
• Step 2: Compute XOR of all elements in perm except the first one.
  If you XOR every encoded[i] where i is odd (i.e., encoded[1], encoded[3], ...), you get the XOR of all perm[1], perm[2], ..., perm[n-1]. This is because each encoded[i] = perm[i] XOR perm[i+1], and the pattern cancels out all elements except the first.
• Step 3: Find the first element of perm.
  The first element is perm[0] = total XOR (XOR of perm[1]...perm[n-1]).
• Step 4: Reconstruct the rest of the permutation.
  Once you have perm[0], you can iterate through encoded and recover each subsequent perm[i+1] = perm[i] XOR encoded[i].

This approach leverages the properties of XOR and avoids brute-force search, making it both elegant and efficient.

Example Walkthrough

Let's walk through an example with encoded = [6,5,4,6].

• Step 1: The length of encoded is 4, so n = 5.
• Step 2: Compute total = 1 XOR 2 XOR 3 XOR 4 XOR 5 = 1^2=3, 3^3=0, 0^4=4, 4^5=1, so total = 1.
• Step 3: Compute XOR of all encoded[i] where i is odd: encoded[1]=5 and encoded[3]=6, so odd = 5 XOR 6 = 3.
• Step 4: perm[0] = total XOR odd = 1 XOR 3 = 2.
• Step 5: Reconstruct the permutation:
  • perm[1] = perm[0] XOR encoded[0] = 2 XOR 6 = 4
  • perm[2] = perm[1] XOR encoded[1] = 4 XOR 5 = 1
  • perm[3] = perm[2] XOR encoded[2] = 1 XOR 4 = 5
  • perm[4] = perm[3] XOR encoded[3] = 5 XOR 6 = 3
• Result: The permutation is [2, 4, 1, 5, 3].

This matches the requirements and uses each number from 1 to 5 exactly once.

Time and Space Complexity

• Brute-force approach: Would require checking all n! permutations, leading to O(n!) time and O(n) space for each attempt.
• Optimized approach:
  • Computing the total XOR and the odd-indexed XOR both take O(n) time.
  • Reconstructing the permutation also takes O(n) time.
  • Space complexity is O(n) for the output array.

Thus, the final solution is O(n) time and O(n) space.

Summary

The Decode XORed Permutation problem is a great example of leveraging the properties of XOR to simplify what might otherwise seem like a complex permutation reconstruction task. By observing how the XOR operation can be reversed and combined, we efficiently recover the original permutation in linear time. The key insight is to compute the total XOR and the odd-indexed XOR to deduce the first element, then iteratively reconstruct the rest. This makes the solution both elegant and highly efficient.