Decode XORed Permutation
Medium · Bit Manipulation · Array · Bit Manipulation
Problem
A hidden array perm is a permutation of the first n positive integers (1 through n), and n is always odd. It was encoded into encoded of length n - 1, where encoded[i] = perm[i] XOR perm[i + 1].
Given only encoded, return the original perm. It is guaranteed to be unique. You are not told the first element, so you need to work it out.
Examples
Input: encoded = [1,2] Output: [2,3,1]
2 XOR 3 = 1 and 3 XOR 1 = 2, and [2,3,1] is a permutation of 1..3.
Input: encoded = [6,4,5,6] Output: [3,5,1,4,2]
Starting from 3, each XOR recovers the next value: 5, 1, 4 and 2.
Input: encoded = [3,1,7,1,3,1] Output: [1,2,3,4,5,6,7]
The codes of 1, 2, …, 7 in order decode back to the sorted permutation.
Constraints
- 3 <= n < 10^5
- n is odd
- encoded.length == n - 1
- encoded comes from a permutation of 1..n
Approaches
- Baseline: try every first value — time O(n^2), space O(n)
Follow-up
XOR cancels anything that appears twice, which is why knowing the set of values recovers the missing start. The use cases compute 1 ^ 2 ^ … ^ n in constant time, and recover an array from its prefix XORs.
Related problems
Start free on Cariara · Coding problems · System design studio
