Generate a uniform random numbers in $O(1)$

Question

Suppose you have access to a random number generator $G()$ that generates uniform random numbers in $\{0,\cdots,n-1\}$. (Here, $n$ is given and cannot be changed.) How do we generate a uniform random number in $\{0,\cdots,m-1\}$ for $m\leq n$? We require that we can only call $G()$ $O(1)$ times in expectation.

My effort: Suppose $n=km+r$, where $k$ and $r$ are integers. Call $G()$. If $G()\leq km$, return $G()\mod m$; otherwise, call $G()$ again.

But in expectation, this will call $G()$ $O(\frac{n}{n-r})$ times, and $r$ can be $1,\cdots,m-1$.

Answer 1

Since $r < m \leq n$, necessarily $k \geq 1$ and so $n - r = km \geq m > r$. In particular, $r < n/2$ and so $n-r > n/2$. In total, we conclude that $n/(n-r) < 2$.