Implement Rand10() Using Rand7() - Solution & Explanation
Problem Statement
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()?
Approach Overview
Problem Overview: You are given an API rand7() that returns a uniform random integer from 1 to 7. The task is to implement rand10(), which must return a uniform random integer from 1 to 10. You cannot modify rand7(); the only tool available is calling it multiple times.
Approach 1: Rejection Sampling Method (Expected O(1) time, O(1) space)
This approach converts the 1–7 generator into a larger uniform sample space. Call rand7() twice to simulate a 7×7 grid (49 equally likely outcomes). Map the pair to a number from 1–49 using (row - 1) * 7 + col. Only the first 40 values are useful because 40 is divisible by 10. If the generated value is ≤ 40, return value % 10 + 1. Otherwise reject the sample and repeat.
The key insight is rejection sampling: discard outcomes that would introduce bias. Because 40 out of 49 values are valid, the loop rarely repeats and the expected runtime remains constant. This technique relies on concepts from rejection sampling, randomized algorithms, and probability and statistics.
Approach 2: Random Walk on a 2D Grid (Expected O(1) time, O(1) space)
Another perspective treats the repeated calls to rand7() as coordinates in a 2D grid. Each pair of calls produces one of 49 equally likely cells. Instead of discarding all values above 40 immediately, you can reuse the leftover region by remapping it into another smaller grid and repeating the process. This creates a "random walk" through progressively smaller sample spaces until a valid number from 1–10 appears.
The advantage is slightly improved efficiency because leftover randomness is reused instead of fully discarded. The algorithm still relies on uniform mapping and rejection of biased states, but it minimizes wasted samples. Time complexity remains expected O(1) with constant O(1) memory since only a few integers are tracked.
Recommended for interviews: The rejection sampling method is the standard solution interviewers expect. It clearly demonstrates how to transform one uniform distribution into another using modular arithmetic and rejection logic. Showing this approach proves you understand probability mapping. Discussing the optimized grid reuse strategy afterward shows deeper knowledge of randomized algorithm design.
Approach 1: Rejection Sampling Method
The rejection sampling method involves generating a larger range of values than needed using multiple calls to rand7(), then rejecting any values that fall outside the desired range. The goal is to convert an output range span (like 1 to 7) to another (like 1 to 10). You can do this by mapping combinations of rand7() outputs together.
The idea is to create a smaller uniform distribution using a larger one and then scale it down to the desired range.
In this C solution, we first generate two random numbers (row and column) using rand7(). We then map these to a single number in the range [1,49]. We repeatedly generate numbers until we get a result in the range [1,40] to ensure uniformity. The final transformation scales this number to [1,10].
Complexity
The expected time complexity is O(1), but the actual time depends on the success rate of generating a number that falls within the desired range. The space complexity is O(1) since we only use a limited amount of storage regardless of input size.
Approach 2: Random Walk on a 2D Grid
This approach explores random walks over a 2D grid formed by two calls to rand7(). By defining a grid dimension and using rerolls for values that fall outside of a specific boundary, it effectively resamples portions of the distribution space.
We consider a grid of 7x7 points and use this combined space to extract valid outcomes for our 1-10 range.
This C solution simulates a random walk over a 2D 7x7 grid. By leveraging grid positions, it discards values outside the boundary, essentially repeating the attempt until a valid number is extracted which can then map consistently to range 1-10.
Complexity
The average time complexity is O(1) due to expected constant writes, but can vary based on rerolls. The space used is fixed so the space complexity is O(1).
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Rejection Sampling Method | The expected time complexity is O(1), but the actual time depends on the success rate of generating a number that falls within the desired range. The space complexity is O(1) since we only use a limited amount of storage regardless of input size. |
| Random Walk on a 2D Grid | The average time complexity is O(1) due to expected constant writes, but can vary based on rerolls. The space used is fixed so the space complexity is O(1). |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Rejection Sampling | Expected O(1) | O(1) | Standard interview solution; simple mapping from 49 outcomes to 10 uniform values |
| Random Walk on 2D Grid (Reuse Leftovers) | Expected O(1) | O(1) | When optimizing rejection sampling to reuse remaining probability space |
Video Solution
Implement Rand10() Using Rand7() | LeetCode 470 | C++, Java, Python • Knowledge Center • 6,816 views views
Watch 9 more video solutions →Frequently Asked Questions
How to solve Implement Rand10() Using Rand7()?
Is Implement Rand10() Using Rand7() easy or hard?
Implement Rand10() Using Rand7() Python/Java solution
What is the best approach for Implement Rand10() Using Rand7()?
Is Implement Rand10() Using Rand7() asked at Google/Amazon/Meta?
What data structure is used in Implement Rand10() Using Rand7()?
What is the time complexity of Implement Rand10() Using Rand7()?
Ready to solve this problem?
Practice Implement Rand10() Using Rand7() with our built-in code editor and test cases.
Practice on FleetCode