Equal Probability between 1 and 7

Question: 

Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. The distribution between each of the numbers must be uniform.

.

.

C

A

P

T

A

I

N

I

N

T

E

R

V

I

E

W

.

.

Solution:

Let’s think of this as a decision tree. Each rand5() will be a decision. After 2 tries, we have 25 possible solutions. We try to get maximum bunches of 7 as we can (1 – 21, 3 sets of 7). If we get any of the other values, we just try again. Since the probability of getting each of 21 values is the same every time, trying again won’t affect their probabilities.

Equal Probability 1 to 7

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

That was fun, right? Anyone up for another challenge? Watch out for it next Tuesday (March 1st).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s