Connor

Hi, I may post some DSA / interview questions I find interesting (even if you would be unlikely to see it in an interview) from some of the books I own / codeforces / leetcode etc.

This question comes from Elements of Programming Interviews in Java written by Lee, Aziz, and Prakash.

4.10 Generate Random Uniform Numbers
How would you implement a random number generator that generates a random integer i between a and b inclusive, given a random number generator that produces a zero or one with equal probability?
ALL values in range [a,b] inclusive should be equally likely.

Hint Given: How would you mimic a three-sided coin with a two-sided coin?

So you are given a 0/1 generator which gives you one of 0 or 1 at a 50% chance with each call to it: int zeroOrOne = generator().

My hint is this: What does b - a represent, and how can you limit the number of calls to the generator?

This is my first post!