# A data structure puzzle (and my solution)

Published on

Jarno Alanko offered this puzzle on twitter:

Here’s my solution. It’s a programmer’s solution: it assumes that integers take $$O(1)$$ space and hash maps allow $$O(1)$$ lookups. If you know a solution that doesn’t make these assumptions, please let me know!

So, consider the decomposition of $$f$$ into disjoint cycles. For every cycle that has $$k > \sqrt{n}$$ elements, arbitrarily pick $$\lceil k / \sqrt{n}\rceil$$ elements—“breakpoints”—such that, when moving along the cycle, the distance between any two breakpoints is at most $$\sqrt{n}$$. Since there are fewer than $$\sqrt{n}$$ such cycles, the total number of breakpoints is

$\sum_i \lceil k_i / \sqrt{n}\rceil < \sum_i (k_i / \sqrt{n}+1) < 2\sqrt{n}.$

Store all the breakpoints in a hash map $$h$$ that maps each breakpoint to the previous breakpoint in the same cycle. Then, to invert an element $$x$$, use the following algorithm:

x1 := x
x2 := f(x)
while (x2 != x):
if h contains x1:
x1 := h(x1)
else:
x1 := x2
x2 := f(x1)
return x1

This algorithm finds the inverse element by iteratively applying $$f$$ until it comes back to $$x$$. The hash map $$h$$ provides a shortcut to instantaneously traverse a large part of the cycle. After less than $$\sqrt{n}$$ iterations, the loop either finds $$x$$ or finds a point $$x_1$$ for which $$h(x_1)$$ is defined. In the latter case, $$x$$ lies (cycle-wise) in the interval $$(h(x_1), x_1)$$, and once the search is restarted from $$h(x_1)$$, it will take less than $$\sqrt{n}$$ additional loop iterations to locate $$x$$.