Problem

Given the API rand7() that generates a uniform random integer in the range [1, 7], write a function rand10() that generates a uniform random integer in the range [1, 10]. You can only call the API rand7(), and you shouldn’t call any other API. Please do not use a language’s built-in random API.

Each test case will have one internal argument n, the number of times that your implemented function rand10() will be called while testing. Note that this is not an argument passed to rand10().

Examples

Example 1:

1
2
3
4

Input:
n = 1
Output:
 [2]

Example 2:

1
2
3
4

Input:
n = 2
Output:
 [2,8]

Example 3:

1
2
3
4

Input:
n = 3
Output:
 [3,8,10]

Solution

Method 1 - Rejection Sampling Method

A common technique for such problems is to use the Rejection Sampling Method. Here we use multiple calls to rand7() to generate a larger range of numbers, which is then utilized to get the desired range [1, 10].

Steps:

  1. Use rand7() twice to generate a number in the larger range [1, 49].
    • The first call to rand7() gives us a range from 1 to 7.
    • The second call to rand7() gives us another range from 1 to 7.
    • Combining these, we get a number in the range [1, 49].
  2. Use rejection sampling to restrict this range appropriately.
    • We only accept numbers from 1 to 40 for simplicity since 40 is a multiple of 10, ensuring each number from 1 to 10 has an equal probability.
    • If we get a number greater than 40, we discard it and retry.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {

	public static int rand10() {
		while (true) {
			// Generate a number in the range [1, 49]
			int num = (rand7() - 1) * 7 + rand7();

			// Only accept numbers in the range [1, 40]
			if (num <= 40) {
				return (num - 1) % 10 + 1;
			}
		}
	}
}

Complexity

  • Time: O(1)
  • Space: O(1)