Decode XORed Permutation — Solution in Python, Java & C++
Decode XORed Permutation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Decode XORed Permutation is a medium coding problem on arrays, bit manipulation and brainteaser, asked in Amazon, Google and Uber interviews.
- Difficulty: Medium
- Topics: Arrays, Bit Manipulation, Brainteaser
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A hidden array perm is a permutation of the first n positive integers, where n is odd. It was encoded as encoded[i] = perm[i] XOR perm[i + 1], giving an array of length n - 1.
Given encoded, return perm. The answer is unique.
Example 1
Input: encoded = [3,1]
Output: [1,2,3]
Explanation: 1 XOR 2 = 3 and 2 XOR 3 = 1.
Example 2
Input: encoded = [6,5,4,6]
Output: [2,4,1,5,3]
Example 3
Input: encoded = []
Output: [1]
Explanation: With n = 1 there is nothing to encode.
Constraints
3 <= n <= 100000n is oddencoded.length == n - 1The input always comes from a valid permutation.
Hints for Decode XORed Permutation
Hint 1
Once you know
perm[0], the rest unrolls:perm[i+1] = perm[i] XOR encoded[i].Hint 2
The XOR of the whole permutation is the XOR of
1 … n, which you can compute directly.Hint 3
The XOR of
encodedat odd indices telescopes toperm[1] XOR perm[2] XOR … XOR perm[n-1].
How to solve Decode XORed Permutation
Recovering perm[0] is the whole problem, and two XOR identities give it. The total XOR of the permutation is known from n, and the odd-indexed entries of encoded pair up the remaining elements exactly once each.
Approach
- Compute
total = 1 XOR 2 XOR … XOR n. - Compute
odd = encoded[1] XOR encoded[3] XOR …, which equalsperm[1] XOR … XOR perm[n-1]. - Then
perm[0] = total XOR odd. - Unroll the rest with
perm[i+1] = perm[i] XOR encoded[i].
Why it works
encoded[1] = perm[1] ^ perm[2], encoded[3] = perm[3] ^ perm[4], and so on — because n is odd there are (n-1)/2 such pairs covering indices 1 … n-1 exactly once. XOR-ing the total by that value cancels everything except perm[0].
Complexity
- Time —
O(n) - Space —
O(n) for the output
Pitfalls
- Using the even indices of
encodeddouble counts and gives the wrong seed. - The trick relies on
nbeing odd; with an evennthe pairing does not cover the tail cleanly. - Trying every possible
perm[0]isO(n²)and times out.
Reference solution
Python
from typing import List
def decodePermutation(encoded: List[int]) -> List[int]:
n = len(encoded) + 1
total = 0
for v in range(1, n + 1):
total ^= v
odd = 0
for i in range(1, len(encoded), 2):
odd ^= encoded[i]
perm = [total ^ odd]
for e in encoded:
perm.append(perm[-1] ^ e)
return permJava
public static int[] decodePermutation(int[] encoded) {
int n = encoded.length + 1;
int total = 0;
for (int v = 1; v <= n; v++) total ^= v;
int odd = 0;
for (int i = 1; i < encoded.length; i += 2) odd ^= encoded[i];
int[] perm = new int[n];
perm[0] = total ^ odd;
for (int i = 0; i < encoded.length; i++) perm[i + 1] = perm[i] ^ encoded[i];
return perm;
}C++
vector<int> decodePermutation(vector<int>& encoded) {
int n = (int) encoded.size() + 1;
int total = 0;
for (int v = 1; v <= n; v++) total ^= v;
int odd = 0;
for (size_t i = 1; i < encoded.size(); i += 2) odd ^= encoded[i];
vector<int> perm(n);
perm[0] = total ^ odd;
for (size_t i = 0; i < encoded.size(); i++) perm[i + 1] = perm[i] ^ encoded[i];
return perm;
}JavaScript
var decodePermutation = function(encoded) {
var n = encoded.length + 1;
var total = 0;
for (var v = 1; v <= n; v++) total ^= v;
var odd = 0;
for (var i = 1; i < encoded.length; i += 2) odd ^= encoded[i];
var perm = [total ^ odd];
for (var j = 0; j < encoded.length; j++) perm.push(perm[j] ^ encoded[j]);
return perm;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Bit Manipulation