1267. Rebuilding a Permutation From Its Neighbouring XORs

A permutation of 1 through n, with n ODD, was replaced by the n - 1 XORs of its adjacent pairs: entry i of the encoding is p[i] ^ p[i+1]. Print the original permutation.

n=3, encoding 3 1 -> 1 2 3 since 1^2 = 3 and 2^3 = 1 n=5, encoding 3 1 7 1 -> 1 2 3 4 5 n=3, encoding 1 3 -> 3 2 1

## What most people try first

Guess p[0], propagate with p[i+1] = p[i] ^ e[i], and check whether the result is a permutation of 1..n. If not, try the next guess. That is correct and it is O(n^2): n candidate first elements, each needing an O(n) propagation and check. At n = 99999 that is about 10^10 steps.

The propagation half of that is right and unavoidable. What has to go is the guessing.

## The encoding determines everything except the first element

Given p[0], the rest follows: p[1] = p[0] ^ e[0], then p[2] = p[1] ^ e[1], and so on. So the entire problem is to find p[0], and exactly one value of it can be right, because the propagation is a bijection.

## Two totals, and the one piece they do not share

Here is where n being odd earns its place in the statement. Since n is odd, n - 1 is even, so the positions 1, 2, ..., n-1 can be grouped into consecutive PAIRS:

(p[1], p[2]), (p[3], p[4]), ..., (p[n-2], p[n-1])

and the XOR of each of those pairs is an entry of the encoding at an ODD index: e[1] = p[1] ^ p[2], e[3] = p[3] ^ p[4], and so on. Therefore

e[1] ^ e[3] ^ e[5] ^ ... = p[1] ^ p[2] ^ ... ^ p[n-1]

which is everything except p[0].

The other total is free: the values are exactly 1..n in some order, so

total = 1 ^ 2 ^ ... ^ n = p[0] ^ p[1] ^ ... ^ p[n-1]

XOR the two and everything but p[0] cancels:

p[0] = total ^ (e[1] ^ e[3] ^ e[5] ^ ...)

Then propagate once. The total can be computed with #1261's closed form or with a loop over 1..n; at these sizes the loop is fine.

## Cost

O(n) time and O(n) space for the output, against O(n^2) for the guessing version. There is nothing to search.

## Width

n is at most 99999, below 2^17, so every permutation value and every XOR of such values is below 2^17. Everything fits in a signed 32-bit integer, whose limit is 2147483647, with four orders of magnitude of headroom, and JavaScript's ^ on plain Numbers is safe because every operand already fits in signed 32 bits. Note that the encoding entries are themselves XORs of two values below 2^17, so they are also below 2^17 and cannot be larger than the values they came from in any way that matters.

Constraints - `1 ≤ n ≤ 99999`, and `n` is odd - the input is the adjacent-pair encoding of some permutation of `1` through `n` - that permutation is unique