Planets Queries I - Walkthrough

Graph: $f(1) = 2, f(2) = 3, f(3) = 4, f(4) = 1$. This forms a cycle of length $4$. Query: start at $1$, go $7$ steps. You need to find where you land. Jump table: $\text{jump}[0] = [2,3,4,1]$, $\text{jump}[1] = [3,4,1,2]$, $\text{jump}[2] = [1,2,3,4]$.

Each row is built from the previous row by composing the function. $k = 7 = 4 + 2 + 1$ in binary: $111$. Start at $1$. Jump $4$: reach $1$. Jump $2$: reach $3$. Jump $1$: reach $4$. Answer: $4$. The binary decomposition makes it efficient.