11.9 Implement Rand10() Using Rand7()

11.9.1 Problem Metadata

11.9.2 Description

Given the API rand7() which generates a uniform random integer in the range [1, 7], write a function rand10() which 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 the system’s built-in random API.

Each testcase 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().

11.9.3 Examples

Input: n = 1
Output: [7]

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

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

11.9.4 Constraints

  • 1 <= n <= 10^5

11.9.5 Follow-up

  • What is the expected value for the number of calls to rand7() function?
  • Could you minimize the number of calls to rand7()?

11.9.6 Solution - Rejection Sampling

11.9.6.1 Walkthrough

The key insight is to generate a uniform distribution over a larger range, then map a subset of it to [1, 10]. Calling rand7() twice gives us 49 equally likely outcomes. We can compute rand49 = (rand7() - 1) * 7 + rand7(), which produces values in [1, 49].

Since 49 is not divisible by 10, we cannot directly map all 49 values uniformly to 10 buckets. Instead, we use the first 40 values (which is divisible by 10) and reject values in [41, 49]. For accepted values in [1, 40], we map them to [1, 10] by computing (rand49 - 1) / 4 + 1, which gives each output value exactly 4 inputs (e.g., 1,2,3,4 -> 1, 5,6,7,8 -> 2, …, 37,38,39,40 -> 10).

When a rejected value occurs, we retry. The probability of acceptance is 40/49 ≈ 81.6%, so the expected number of iterations is 49/40 ≈ 1.225, meaning we call rand7() an average of ~2.45 times per rand10() call.

11.9.6.2 Analysis

  • Time Complexity: O(1) expected (geometric distribution with success probability 40/49)
  • Space Complexity: O(1)

11.9.6.3 Implementation Steps

  1. Call rand7() twice to generate rand49 = (rand7() - 1) * 7 + rand7(), producing a uniform distribution over [1, 49].
  2. If rand49 > 40, reject and retry (rejection sampling to ensure uniform distribution).
  3. Map accepted values [1, 40] to [1, 10] via (rand49 - 1) / 4 + 1, giving each output exactly 4 inputs.
  4. Return the mapped value.

11.9.6.4 Code - Java

/**
 * The rand7() API is already defined in the parent class SolBase.
 * public int rand7();
 * @return a random integer in the range 1 to 7
 */
class Solution extends SolBase {
    public int rand10() {
        while (true) {
            // rand49 = ([1..7] - 1) * 7 + [1..7] = [1..49]
            int rand49 = (rand7() - 1) * 7 + rand7();

            // reject samples if rand49 > 40
            if (rand49 <= 40) {
                // [1..40] -> (rand49-1)/4 + 1 maps to [1..10] with 4 values each
                // 1, 2, 3, 4 -> 1, 
                // 5, 6, 7, 8 -> 2, 
                // ...
                // 37,38,39,40 -> 10
                return (rand49 - 1) / 4 + 1;
            }
        }
    }
}