Decode XORed Permutation - Solution & Explanation
Problem Statement
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 < 105nis odd.encoded.length == n - 1
Approach Overview
Problem Overview: You receive an array encoded where encoded[i] = perm[i] XOR perm[i+1]. The original array perm is a permutation of numbers from 1 to n and n is odd. The task is to reconstruct the entire permutation. The challenge is recovering the first element efficiently using XOR properties.
Approach 1: Brute Force Guessing (O(n^2) time, O(1) space)
One direct idea is to try every possible value from 1 to n as the first element of the permutation. Once the first element is fixed, the rest of the array can be reconstructed because perm[i+1] = perm[i] XOR encoded[i]. After generating the candidate permutation, verify whether it forms a valid permutation containing every number from 1 to n exactly once. This works because XOR uniquely determines the next element when the previous value is known. However, validating permutations repeatedly pushes the complexity to O(n^2), which is unnecessary given the constraints.
Approach 2: Determine Total XOR (O(n) time, O(1) space)
The optimal strategy relies on XOR properties and the fact that the array is a permutation of 1..n. First compute the XOR of all numbers from 1 to n. This represents perm[0] XOR perm[1] XOR ... XOR perm[n-1]. Next, compute the XOR of all elements at odd indices in encoded (encoded[1] ^ encoded[3] ^ ...). Expanding these terms cancels many values and leaves perm[1] XOR perm[2] XOR ... XOR perm[n-1].
Now XOR the two results. The overlapping elements cancel out, leaving only perm[0]. Once the first value is known, reconstruct the rest of the permutation by iterating through the encoded array and applying perm[i+1] = perm[i] ^ encoded[i]. This approach performs a few linear passes over the array and uses constant extra memory.
This technique works because XOR is associative and self-inverting (a ^ a = 0). Those properties allow large portions of the permutation to cancel out during aggregation. Problems like this often appear in Bit Manipulation practice and combine XOR tricks with simple iteration over an Array. The reconstruction step is essentially a forward pass similar to computing values from a prefix XOR relationship.
Recommended for interviews: The total XOR method is the expected solution. Interviewers want to see that you recognize XOR cancellation and use the permutation constraint to recover the first element. Mentioning the brute force idea shows reasoning, but deriving the O(n) XOR trick demonstrates strong problem-solving skills.
Approach 1: Approach 1: Determine Total XOR
This method utilizes the properties of XOR to find the first element of the permutation. Since perm is a permutation of the first n positive integers, compute the total XOR of numbers from 1 to n. Calculate the XOR of the encoded array at every alternate index (odd positions really give us the XOR excluding perm[0]). The difference gives us the first element of perm, and from there, remaining permutation elements can be deduced.
The solution first calculates the XOR of all numbers from 1 to n. It then computes the XOR of encoded elements at odd indices which helps in isolating perm[0]. Next, it computes the first element using XOR properties. Subsequently, it utilizes a loop to deduce perm from encoded.
Complexity
Time Complexity: O(n), as there are two traversals over the arrays. Space Complexity: O(1), excluding the space needed for the output.
Approach 2: Bitwise Operation
We notice that the array perm is a permutation of the first n positive integers, so the XOR of all elements in perm is 1 \oplus 2 \oplus cdots \oplus n, denoted as a. And encode[i]=perm[i] \oplus perm[i+1], if we denote the XOR of all elements encode[0],encode[2],cdots,encode[n-3] as b, then perm[n-1]=a \oplus b. Knowing the last element of perm, we can find all elements of perm by traversing the array encode in reverse order.
The time complexity is O(n), where n is the length of the array perm. Ignoring the space consumption of the answer, the space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Determine Total XOR | Time Complexity: O(n), as there are two traversals over the arrays. Space Complexity: O(1), excluding the space needed for the output. |
| Bitwise Operation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Guess First Element | O(n^2) | O(1) | Conceptual baseline to understand reconstruction from XOR relations |
| Determine Total XOR (Optimal) | O(n) | O(1) | General case. Uses XOR properties and permutation constraint for optimal decoding |
Video Solution
Leetcode 1734. Decode XORed Permutation • Fraz • 2,903 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Decode XORed Permutation easy or hard?
Decode XORed Permutation Python/Java solution
How to solve Decode XORed Permutation in O(n)?
What is the best approach for Decode XORed Permutation?
Is Decode XORed Permutation asked at Google/Amazon/Meta?
What data structure is used in Decode XORed Permutation?
What is the time complexity of Decode XORed Permutation?
Ready to solve this problem?
Practice Decode XORed Permutation with our built-in code editor and test cases.
Practice on FleetCode