Generate a uniform random numbers in $O(1)$
Since $r &lt; m \leq n$, necessarily $k \geq 1$ and so $n - r = km \geq m &gt; r$. In particular, $r &lt; n/2$ and so $n-r &gt; n/2$. In total, we conclude that $n/(n-r) &lt; 2$.