Decode XORed Permutation

MEDIUM

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.

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

Approaches

Checkout 2 different approaches to solve Decode XORed Permutation. Click on different approaches to view the approach and algorithm in detail.

Finding the First Element using XOR Properties

This optimal approach cleverly uses the properties of the XOR operation to determine the first element of the permutation, perm[0], directly. By finding perm[0], the rest of the array can be decoded in a single pass. This avoids the trial-and-error of the brute-force method.

Algorithm

Determine the size of the permutation, n = encoded.length + 1.
Calculate total_xor, the XOR sum of all integers from 1 to n.
Calculate odd_indices_xor, the XOR sum of all elements in the encoded array that are at odd indices (encoded[1], encoded[3], etc.).
Determine the first element of the permutation, perm[0], by XORing the two results: perm[0] = total_xor XOR odd_indices_xor.
Create the result array perm of size n and place perm[0] at the first position.
Iterate from i = 0 to n-2 and compute the subsequent elements: perm[i+1] = perm[i] XOR encoded[i].
Return the fully constructed perm array.

The key insight is to relate the XOR sum of all elements in the permutation to the XOR sum of elements in the encoded array.

Total XOR Sum: Since perm is a permutation of 1, 2, ..., n, the XOR sum of all its elements is known: total_xor = 1 XOR 2 XOR ... XOR n.
Relating to encoded: The encoded array is defined as encoded[i] = perm[i] XOR perm[i+1]. Let's consider the XOR sum of elements of encoded at odd indices: encoded[1] XOR encoded[3] XOR ... XOR encoded[n-2]. (Note: n is odd, so n-2 is also odd). This sum expands to: (perm[1] XOR perm[2]) XOR (perm[3] XOR perm[4]) XOR ... XOR (perm[n-2] XOR perm[n-1]). Due to the associative property of XOR, this simplifies to perm[1] XOR perm[2] XOR ... XOR perm[n-1]. This is the XOR sum of all elements in perm except perm[0].
Finding perm[0]: We have two equations:
- total_xor = perm[0] XOR perm[1] XOR ... XOR perm[n-1]
- odd_indices_xor = perm[1] XOR perm[2] XOR ... XOR perm[n-1] If we XOR these two values together: total_xor XOR odd_indices_xor = (perm[0] XOR ... XOR perm[n-1]) XOR (perm[1] XOR ... XOR perm[n-1]) The terms perm[1] through perm[n-1] appear twice and cancel out (since x XOR x = 0), leaving only perm[0]. Thus, perm[0] = total_xor XOR odd_indices_xor. Once we calculate perm[0], we can find the rest of the elements sequentially: perm[i] = perm[i-1] XOR encoded[i-1].

class Solution {
    public int[] decode(int[] encoded) {
        int n = encoded.length + 1;
        int[] perm = new int[n];

        // 1. Calculate the XOR sum of the permutation (1 XOR 2 XOR ... XOR n)
        int total_xor = 0;
        for (int i = 1; i <= n; i++) {
            total_xor ^= i;
        }

        // 2. Calculate the XOR sum of elements at odd indices in 'encoded'
        // This gives us perm[1] ^ perm[2] ^ ... ^ perm[n-1]
        int odd_indices_xor = 0;
        for (int i = 1; i < encoded.length; i += 2) {
            odd_indices_xor ^= encoded[i];
        }

        // 3. Find the first element of the permutation
        // perm[0] = total_xor ^ odd_indices_xor
        perm[0] = total_xor ^ odd_indices_xor;

        // 4. Reconstruct the rest of the permutation
        for (int i = 0; i < n - 1; i++) {
            perm[i + 1] = perm[i] ^ encoded[i];
        }

        return perm;
    }
}

Complexity Analysis

Time Complexity: O(n), where `n` is the size of the permutation. Calculating `total_xor` takes O(n), calculating `odd_indices_xor` takes O(n), and reconstructing the final `perm` array takes O(n). The overall complexity is linear.Space Complexity: O(n) to store the output `perm` array. If the output array is not considered part of the space complexity, the algorithm uses O(1) extra space.

Pros and Cons

Pros:

Highly efficient with linear time complexity, making it suitable for large inputs.
Guaranteed to find the unique solution directly without searching.

Cons:

The logic relies on a non-obvious mathematical property of the XOR operation, which can be difficult to derive during an interview.

Code Solutions

Checking out 3 solutions in different languages for Decode XORed Permutation. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Decode XORed Permutation

Patterns:

Bit Manipulation

Data Structures:

Array