© Parineeth M R

** Question 51. Suppose you are given a random number generator that generates numbers uniformly in the range 1 to 5. How will you generate numbers uniformly in the range 1 to 7?**

Let’s us say that we are provided with the rand5() function that generates values uniformly from 1 to 5. We can generate values uniformly from 0 to 4 by subtracting 1 from the result of rand5(). Now using rand5() we can uniformly generate numbers in the range 0 to 24 using the following formula

(rand5() – 1) + 5 * (rand5() – 1)

Now to generate numbers uniformly from 1 to 7, we use rejection sampling. If the above formula generates a random number in the range 0 to 20, we accept the number. If the formula generates a number in the range 21 to 24, then we reject the number and re-try the formula till we get a number in the range 0 to 20. We then find the remainder when the number in range 0 to 20 is divided with 7. The remainder will be uniformly distributed in the range 0 to 6. We then add 1 to the remainder to get the result which will be uniformly distributed in the range 1-7.

The rejection sampling in this case can be visualized with a 5 * 5 grid, where in if we throw a dart and the dart randomly lands on a cell, the number in the grid is accepted for some cells and rejected for others.

## C/C++

int rand7() { int result; while(1) { result = (rand5() - 1) + (5 * (rand5() - 1) ); if (result <= 20) break; } result = 1 + (result % 7); return result; }

## Java

public static int rand7() { int result; while(true) { result = (rand5() - 1) + (5 * (rand5() - 1)); if (result <= 20) break; } result = 1 + (result % 7); return result; }

## Python

def rand7() : while(True) : result = (rand5() - 1) + (5 * (rand5() - 1)) if (result <= 20): break result = 1 + (result % 7) return result

I hope you liked the article. ** I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book**, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the **Amazon Giveaway** link to you. **If you like the book please give your review comments on Amazon**. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.