# Given random5(), implement random7()

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 arandomuniformly distributedfrom 1 to 7.integer

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.