Watch 10 video solutions for Decode XORed Permutation, a medium level problem involving Array, Bit Manipulation. This walkthrough by Fraz has 2,888 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 < 105n is odd.encoded.length == n - 1Problem 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 | 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 |