Binary Representation Core Idea

Here is the core idea: any number $k$ can be written as a sum of powers of $2$. For example, $13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0$. To jump up $13$ steps, you could jump $8$ steps, then $4$, then $1$. That is only $3$ jumps instead of $13$. This works because every number has at most $\log k$ bits in its binary representation.

So you need at most $\log k$ jumps. For $k$ up to $10^5$, that is at most $17$ jumps per query.