- Published on

# Implement rand7 using rand5

- Authors
- Name
- Bhuwan Prasad Upadhyay
- @IAmVuwan

## Introduction

Using a function rand5() that returns an integer from 1 to 5 (inclusive) with uniform probability, implement a function rand7() that returns an integer from 1 to 7 (inclusive).

Do NOT use system's Math.random()

## Example

```
Input: 2
Output: [7,4]
Input: 3
Output: [3,1,7]
```

## Solution - by Rejection Sampling

This solution is based upon Rejection Sampling. The main idea is when you generate a number in the desired range, output that number immediately. If the number is out of the desired range, reject it and re-sample again. As each number in the desired range has the same probability of being chosen, a uniform distribution is produced. Obviously, we have to run rand5() function at least twice, as there are not enough numbers in the range of 1 to 7. By running rand5() twice, we can get integers from 1 to 25 uniformly. Since 25 is not a multiple of 7, we have to use rejection sampling. Our desired range is integers from 1 to 21, which we can return the answer immediately. If not (the integer falls between 22 to 25), we reject it and repeat the whole process again.

```
class Solution {
/**
* @return random integer 1 to 5 (inclusive) with uniform (or equal) probability
*/
private int rand5() {
int min = 1;
int max = 5;
Random r = new Random();
return r.nextInt((max - min) + 1) + min;
}
int rand7() {
int row, col, idx;
do {
row = rand5();
col = rand5();
idx = col + (row - 1) * 5;
} while (idx > 21);
return 1 + (idx - 1) % 7;
}
}
```

## Test Cases

```
class SolutionTest {
private Solution solution;
@BeforeEach
void setUp() {
this.solution = new Solution();
}
@Test
void testSolution() {
IntStream.range(0, 1000)
.mapToObj(value -> this.solution.rand7())
.forEach(random -> {
assertTrue(
random > 0 && random <= 7,
String.format("random number: %d -> is not in range {1, 7} inclusive", random)
);
});
}
}
```

## Analysis

- Time Complexity: O(1) average, but O(∞) worst case.
- Space Complexity: O(1)