Decode XORed Permutation — Medium Problem & Solution

A hidden array perm is a permutation of the first n positive integers, where n is odd.

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 <= 100000
n is odd
encoded.length == n - 1
The input always comes from a valid permutation.

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 equals perm[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 encoded double counts and gives the wrong seed.
The trick relies on n being odd; with an even n the pairing does not cover the tail cleanly.
Trying every possible perm[0] is O(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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue