{x}
blog image

Implement Rand10() Using Rand7()

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

 

Example 1:

Input: n = 1
Output: [2]

Example 2:

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

Example 3:

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

 

Constraints:

  • 1 <= n <= 105

 

Follow up:

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

Solution Explanation

This problem requires generating a uniform random integer between 1 and 10 using only a function rand7() that generates a uniform random integer between 1 and 7. The solution utilizes the concept of Rejection Sampling.

Approach:

  1. Generating a Larger Range: We generate a random number in a range that's a multiple of 10. Since rand7() provides numbers from 1 to 7, we can combine two calls to rand7() to create a number in the range 1 to 49 (7 * 7 = 49). This is done by:

    • i = rand7() - 1: Generates a number from 0 to 6.
    • j = rand7(): Generates a number from 1 to 7.
    • x = i * 7 + j: Combines i and j to produce a number from 1 to 49.

  2. Rejection Sampling: The range 1 to 49 isn't perfectly divisible by 10. Numbers 41 to 49 are outside the desired range (1 to 40). If x falls within this unwanted range, we reject it and repeat the process. This ensures uniformity.

  3. Mapping to the Desired Range: If x is within the acceptable range (1 to 40), we map it to the range 1 to 10 using the modulo operator: x % 10 + 1. This gives us a uniform distribution because we've effectively divided the 40 acceptable numbers into four groups of 10.

Time Complexity Analysis:

The time complexity is not deterministic because of the rejection sampling. In the worst case, it might take multiple iterations to get a number within the acceptable range (1 to 40). However, the expected number of calls to rand7() is relatively small.

Let's calculate the expected number of calls to rand7():

  • The probability of getting a number from 1 to 40 is 40/49.
  • The probability of needing to reject and retry is 9/49.

The expected number of times we need to run the loop is given by the geometric distribution:

E[number of iterations] = 1 / P(success) = 49/40 ≈ 1.225

Each iteration calls rand7() twice. Therefore, the expected number of calls to rand7() is approximately 2 * 1.225 = 2.45.

Space Complexity Analysis:

The space complexity is O(1) because we are only using a constant amount of extra space to store variables.

Code Examples: (provided in the problem statement) The code examples in Python, Java, C++, Go, TypeScript, and Rust all implement the algorithm described above. They differ only in syntax, but the core logic remains the same.

Follow-up Questions:

  • Expected Value for the Number of Calls to rand7(): As calculated above, the expected value is approximately 2.45.

  • Minimizing the Number of Calls to rand7(): The provided solution is quite efficient, and it's difficult to significantly improve upon the expected number of calls while maintaining uniformity. More sophisticated techniques might offer marginal improvements, but they would likely add complexity and might not be worth the added effort for a problem with such small expected calls.