 # Given random5(), implement random7()

Published , updated
Tags:

This article looks at the interview question - Given the function random5 that generates and returns a uniformly distributed random integer from 1 to 5, implement random7 that returns a uniformly distributed random integer from 1 to 7.

This is a classic probability problem that turns out to be deceptively tricky since solutions that seem fine don’t end up filling the uniformly distributed requirement.

## Analysis

To start off, let’s reread what we’re supposed to do:

implement random7 that returns a uniformly distributed random integer from 1 to 7.

We’re dealing with integers not floats, so it’s not as simple as multiplying random5 by 7/5. It also needs to be uniformly distributed just like random5, meaning we cannot just return the result of random5() * 2 % 7 + 1 since that will favour the integers 2, 3 and 4 twice as much as the rest.

How about this then?

(random5() + random5() + random5() + random5() + random5() + random5() + random5()) % 7 + 1


This turns out to be a very common answer to the problem, but does each number have an equal chance of being generated?

random5 gives a 20\% chance to return each of the numbers from 1 to 5. Adding random5 7 times will give up a number from 7 to 35. In order to get the value 7, we need to ‘roll’ 1 every time random5 is called which would be 0.2^{7} = 0.00128\% chance, this is also the chance of any particular permutation of rolls occurring. Whereas the value 8 can be generated by rolling 1 on 6 of the calls to random5 and 2 on the other one, giving up a possible 7 different permutations that could occur and therefore a 0.2^{7} \cdot 7 = 0.00896\% chance of occurring.

This trend continues, leading to the middle numbers having a larger chance of occuring.

A good solution to the problem would be to look at it like a decision tree. Calling random5 once to get 5 choices (20\% chance each) that are then split up into another 5 choices (4\% chance each). Giving 25 choices in total, each of which map to a particular action.

Choice number Action
1-21 Return choice number % 7 + 1
22-25 Return random7()

With this solution, in a single call each number has a 12\% chance of returning and there is a 16\% chance that random7() will be called again recursively and returned.

## Code

public static int random5() {
return new Random().nextInt(5) + 1;
}

public static int random7() {
// Get 0, 5, 10, 15 or 20 then add 0-4 (4% chance for 0-24)
int val = (random5() - 1) * 5 + (random5() - 1);
// If 0-20, return the result modulo 7 + 1 (12% chance for 1-7), otherwise
// call recursively (16% chance)
return val >= 21 ? random7() : val % 7 + 1;
}
function random7(random5) {
// Get 0, 5, 10, 15 or 20 then add 0-4 (4% chance for 0-24)
var val = (random5() - 1) * 5 + (random5() - 1);
// If 0-20, return the result modulo 7 + 1 (12% chance for 1-7), otherwise
// call recursively (16% chance)
return val >= 21 ? random7(random5) : val % 7 + 1;
}

## Textbooks

Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) which provides a much deeper, math heavy look.

## Comments

comments powered by Disqus