You are a programmer, you want to make a function rand(n) that takes an integer n>1 and returns a random integer in the range {1...n} with uniform probability.

At you disposal is a binary random number generator which generates 0's and 1's with equal probability (a fair coin) you can use it as many times as you want.

Can you do this and guarantee your program won't run forever?

Posted

You are a programmer, you want to make a function rand(n) that takes an integer n>1 and returns a random integer in the range {1...n} with uniform probability.

At you disposal is a binary random number generator which generates 0's and 1's with equal probability (a fair coin) you can use it as many times as you want.

Can you do this and guarantee your program won't run forever?

## Share this post

## Link to post

## Share on other sites