Scale Engineer

Decode XORed Permutation

Med
#1588Time: 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: 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.
Patterns
Bit Manipulation
Data structures
Array

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

  1. 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.
  2. 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].
  3. 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

Time

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem