#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.
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 arrayperm. It is guaranteed that the answer exists and is unique.
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.
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 permexceptperm[0].
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].
1class Solution {2 public int[] decode(int[] encoded) {3 int n = encoded.length + 1;4 int[] perm = new int[n];56 // 1. Calculate the XOR sum of the permutation (1 XOR 2 XOR ... XOR n)7 int total_xor = 0;8 for (int i = 1; i <= n; i++) {9 total_xor ^= i;10 }1112 // 2. Calculate the XOR sum of elements at odd indices in 'encoded'13 // This gives us perm[1] ^ perm[2] ^ ... ^ perm[n-1]14 int odd_indices_xor = 0;15 for (int i = 1; i < encoded.length; i += 2) {16 odd_indices_xor ^= encoded[i];17 }1819 // 3. Find the first element of the permutation20 // perm[0] = total_xor ^ odd_indices_xor21 perm[0] = total_xor ^ odd_indices_xor;2223 // 4. Reconstruct the rest of the permutation24 for (int i = 0; i < n - 1; i++) {25 perm[i + 1] = perm[i] ^ encoded[i];26 }2728 return perm;29 }30}
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.
This approach involves iterating through all possible values for the first element of the permutation, which must be a number from 1 to n. For each guess, we reconstruct the entire permutation array using the given encoded array. We then check if the reconstructed array is a valid permutation (i.e., contains each number from 1 to n exactly once). Since the solution is guaranteed to be unique, the first valid permutation we find is the answer.
Algorithm
Determine the size of the permutation, n = encoded.length + 1.
Iterate through each integer p0 from 1 to n as a potential candidate for perm[0].
For each p0:
Create a candidate array perm of size n and set perm[0] = p0.
Calculate the remaining elements of perm using the formula: perm[i] = perm[i-1] XOR encoded[i-1] for i from 1 to n-1.
Check if the generated perm is a valid permutation of 1 to n. This can be done by using a HashSet to track seen numbers and ensure there are no duplicates and all numbers are within the range [1, n].
If the perm is valid, return it as the answer.
Walkthrough
The core of this method is trial and error. We know perm[0] has to be one of the integers in [1, 2, ..., n]. We can systematically try each of these n possibilities.
For a given guess p0 for perm[0], we can derive the rest of the perm array using the relationship perm[i] = perm[i-1] XOR encoded[i-1]. After constructing a full candidate perm array, we must validate it. A valid perm array must be a permutation of [1, 2, ..., n], meaning it contains each of these numbers exactly once and no other numbers. We can use a HashSet or a frequency array to check for duplicates and ensure all numbers are within the valid range [1, n]. The first guess for perm[0] that results in a valid permutation gives us our final answer.
1import java.util.HashSet;2import java.util.Set;34class Solution {5 public int[] decode(int[] encoded) {6 int n = encoded.length + 1;7 int[] perm = new int[n];89 // Iterate through all possible values for the first element10 for (int first = 1; first <= n; first++) {11 perm[0] = first;1213 // Generate the rest of the permutation14 for (int i = 0; i < n - 1; i++) {15 perm[i + 1] = perm[i] ^ encoded[i];16 }1718 // Validate the generated permutation19 if (isValidPermutation(perm, n)) {20 return perm;21 }22 }2324 return new int[0]; // Should not be reached as a solution is guaranteed25 }2627 private boolean isValidPermutation(int[] perm, int n) {28 Set<Integer> seen = new HashSet<>();29 for (int num : perm) {30 if (num < 1 || num > n || !seen.add(num)) {31 return false; // Invalid number or duplicate found32 }33 }34 return seen.size() == n;35 }36}
Complexity
Time
O(n^2), where `n` is the size of the permutation array. The outer loop runs `n` times. For each iteration, we generate a new permutation (O(n)) and then validate it (O(n) using a HashSet). This results in a total complexity of O(n * (n + n)) = O(n^2).
Space
O(n) to store the candidate `perm` array and the `HashSet` used for validation.
Trade-offs
Pros
Conceptually simple and straightforward to implement.
Cons
Inefficient for large values of n. Given the constraint n < 10^5, this approach will be too slow and result in a 'Time Limit Exceeded' error.
Solutions
Solution
1class 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 ; } }
1class Solution { public: vector < int > decode ( vector < int >& encoded ) { int n = encoded . size () + 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 ; } vector < int > perm ( n ); perm [ n - 1 ] = a ^ b ; for ( int i = n - 2 ; ~ i ; -- i ) { perm [ i ] = encoded [ i ] ^ perm [ i + 1 ]; } return perm ; } };
1class Solution : def decode ( self , encoded : List [ int ]) -> List [ int ]: n = len ( encoded ) + 1 a = b = 0 for i in range ( 0 , n - 1 , 2 ): a ^= encoded [ i ] for i in range ( 1 , n + 1 ): b ^= i perm = [ 0 ] * n perm [ - 1 ] = a ^ b for i in range ( n - 2 , - 1 , - 1 ): 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.
