Implement rand5() using rand7()

Problem

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

Examples

Example 1

Solution

Method 1 - Using rejection sampling

The idea is to use rand7() to generate numbers from 1 to 7, and map these numbers to values between [1, 5]. We need to ensure that the probabilities remain uniform despite the discrepancy between the range of 7 and 5, and we can use acceptance-rejection method to avoid bias.

Here is the Acceptance-rejection method:

Generate a Uniform Random Number:
- Call rand7() to get a number.
Reject Unwanted Values:
- If the number generated by rand7() is within the desired range (1 to 5), return it.
- If the number is outside the desired range (6 or 7), reject it and retry.

Rationale Behind Rejection Sampling:

By rejecting the numbers 6 and 7, we ensure that each number from 1 to 5 has an equal probability of 1/5 once accepted.
The rejection rule removes the bias introduced by the additional numbers (6 and 7) which are not needed for rand5().

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public class RandomGenerator {
	public static int rand7() {
		Random rand = new Random();
		return rand.nextInt(7) + 1; 
	}

	public static int rand5() {
		while (true) {
			int num = rand7();

			if (num <= 5) {
				return num;
			}
		}
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
import random


def rand7():
    return random.randint(1, 7)


def rand5():
    while True:
        num = rand7()
        if num <= 5:
            return num

Complexity

⏰ Time complexity: O(1)
🧺 Space complexity: O(1)

Problem#

Examples#

Example 1#

Solution#

Method 1 - Using rejection sampling#

Code#

Complexity#