DSA | Random Generator | Can you come up with a solution?

작성자

카테고리:

← 피드로
DEV Community · Connor · 2026-07-30 개발(SW)

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!

원문에서 계속 ↗

코멘트

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다