1734. Decode XORed Permutation
SourceBiweekly Contest 44 Q3DifficultyMediumRating2024
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 < 105nis odd.encoded.length == n - 1
Solutions
Solution 1: Bitwise Operation
Thinking
\(\textit{perm}\) is a permutation of \(1..n\) with \(n\) odd, and \(\textit{encoded}[i]=\textit{perm}[i]\oplus\textit{perm}[i+1]\). Without one endpoint we cannot recur.
\(1\oplus\cdots\oplus n\) is known. XOR of even indices of \(\textit{encoded}\) omits exactly \(\textit{perm}[n-1]\), recovering the last value.
Walk backward with \(\textit{perm}[i]=\textit{encoded}[i]\oplus\textit{perm}[i+1]\).
We notice that the array \(\textit{perm}\) is a permutation of the first \(n\) positive integers, so the XOR of all elements in \(\textit{perm}\) is \(1 \oplus 2 \oplus \cdots \oplus n\), denoted as \(a\). And \(\textit{encode}[i]=\textit{perm}[i] \oplus \textit{perm}[i+1]\), if we denote the XOR of all elements \(\textit{encode}[0],\textit{encode}[2],\cdots,\textit{encode}[n-3]\) as \(b\), then \(\textit{perm}[n-1]=a \oplus b\). Knowing the last element of \(\textit{perm}\), we can find all elements of \(\textit{perm}\) by traversing the array \(\textit{encode}\) in reverse order.
The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{perm}\).
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |