Implement Rand10() Using Rand7() solution and explanation
Google
9 more videos on this problem
Implement Rand10() Using Rand7() | LeetCode 470 | C++, Java, PythonKnowledge Center · 10:43 · 6K views
花花酱 LeetCode 470. Implement Rand10() Using Rand7() - 刷题找工作 EP226Hua Hua · 12:00 · 4K views
Implement Rand10() Using Rand7() | Leet code 470 | Theory explained + Python & C codeSai Anish Malla · 10:19 · 2K views
Implement Rand10() Using Rand7() | leetcode 470 | HindiCodebix · 8:21 · 2K views
Leetcode - Implement Rand10() Using Rand7() (Python)Timothy H Chang · 8:51 · 1K views
Implement Rand10() Using Rand7() | Day 28 | [ August LeetCoding Challenge ] [ Leetcode ] [ 2020 ]Algorithms Made Easy · 4:25 · 1K views
LeetCode: Implement Rand10 using Rand7 ExampleLeslie Tang · 6:53 · 1K views
Implement Rand10() Using Rand7() | Leetcode August Challenge (Day 28) | Leetcode 470Coding Decoded · 3:32 · 563 views
Daily Leetcode #150: Aug 28, 2020 - 470. Implement Rand10() Using Rand7()Programming Live with Larry · 9:30 · 355 views
Leetcode 470. Implement Rand10() Using Rand7()Kacy Codes · 21:37 · 345 views
The 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().
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.
def rand10():
while True:
row = rand7()
col = rand7()
result = (row - 1) * 7 + col
if result <= 40:
return 1 + (result - 1) % 10class Solution {
public int rand10() {
int result;
do {
int row = rand7();
int col = rand7();
result = (row - 1) * 7 + col;
} while (result > 40);
return 1 + (result - 1) % 10;
}
}int rand7();
int rand10() {
int result;
do {
int row = rand7();
int col = rand7();
result = (row - 1) * 7 + col;
} while (result > 40);
return 1 + (result - 1) % 10;
}function rand10() {
while (true) {
let row = rand7();
let col = rand7();
let result = (row - 1) * 7 + col;
if (result <= 40) {
return 1 + (result - 1) % 10;
}
}
}#include <stdio.h>
int rand7();
int rand10() {
int result;
do {
int row = rand7();
int col = rand7();
result = (row - 1) * 7 + col;
} while (result > 40);
return 1 + (result - 1) % 10;
}public class Solution {
public int Rand10() {
int result;
do {
int row = Rand7();
int col = Rand7();
result = (row - 1) * 7 + col;
} while (result > 40);
return 1 + (result - 1) % 10;
}
}In the Python implementation, the sequence of rand7() calls expands the probability space to 49 possible outcomes. It rejects any number greater than 40, limiting the effect of bias when scaling to a 1-10 outcome range.
This solution runs in expected O(1) time, but in practical cases can retry several times. Space complexity remains O(1).
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.
def rand10():
while True:
num = 7 * (rand7() - 1) + rand7()
if num <= 40:
return num % 10 + 1class Solution {
public int rand10() {
int num;
do {
num = 7 * (rand7() - 1) + rand7();
} while (num > 40);
return num % 10 + 1;
}
}int rand7();
int rand10() {
int num;
do {
num = 7 * (rand7() - 1) + rand7();
} while (num > 40);
return num % 10 + 1;
}function rand10() {
while (true) {
let num = 7 * (rand7() - 1) + rand7();
if (num <= 40) {
return num % 10 + 1;
}
}
}#include <stdio.h>
int rand7();
int rand10() {
int num;
do {
num = 7 * (rand7() - 1) + rand7();
} while (num > 40);
return num % 10 + 1;
}public class Solution {
public int Rand10() {
int num;
do {
num = 7 * (Rand7() - 1) + Rand7();
} while (num > 40);
return num % 10 + 1;
}
}Python implements this approach using a two-layer grid where each cell generated ultimately leads to a suitable number range through rejections/re-rolls directed at errors outside 1-40.
An average time complexity of O(1) is achieved although affected by the grid's boundary conditions. Space remains O(1).
Approach 3: Default Approach
/**
* The rand7() API is already defined for you.
* function rand7(): number {}
* @return a random integer in the range 1 to 7
*/
function rand10(): number {
while (true) {
const i = rand7() - 1;
const j = rand7();
const x = i * 7 + j;
if (x <= 40) {
return (x % 10) + 1;
}
}
}func rand10() int {
for {
i := rand7() - 1
j := rand7()
x := i*7 + j
if x <= 40 {
return x%10 + 1
}
}
}/**
* The rand7() API is already defined for you.
* @return a random integer in the range 1 to 7
* fn rand7() -> i32;
*/
impl Solution {
pub fn rand10() -> i32 {
loop {
let i = rand7() - 1;
let j = rand7();
let x = i * 7 + j;
if x <= 40 {
return (x % 10) + 1;
}
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Rejection Sampling Method | This solution runs in expected O(1) time, but in practical cases can retry several times. Space complexity remains O(1). |
| Random Walk on a 2D Grid | An average time complexity of O(1) is achieved although affected by the grid's boundary conditions. Space remains O(1). |
| Default Approach | – |
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 |
Frequently asked questions
How to solve Implement Rand10() Using Rand7()?
Simulate a larger uniform range using two rand7() calls. Convert them into a number from 1 to 49 with (row−1)*7 + col. Accept values ≤ 40 and return value % 10 + 1. Reject values above 40 and repeat until a valid number appears.
Is Implement Rand10() Using Rand7() easy or hard?
The problem is typically rated Medium. The coding itself is short, but recognizing that you must generate a larger uniform space (1–49) and apply rejection sampling requires understanding of probability and randomized algorithms.
Implement Rand10() Using Rand7() Python/Java solution
Most implementations call rand7() twice, compute (rand7() - 1) * 7 + rand7(), and repeat until the value is ≤ 40. Then return value % 10 + 1. The same logic works in Python, Java, C++, C#, and JavaScript because it only depends on integer arithmetic.
What is the best approach for Implement Rand10() Using Rand7()?
The standard approach is rejection sampling. Call rand7() twice to generate a uniform value from 1 to 49, keep values from 1 to 40, and map them to 1–10 using modulo. This guarantees uniform distribution and runs in expected O(1) time with constant space.
Is Implement Rand10() Using Rand7() asked at Google/Amazon/Meta?
Randomized probability problems like this appear frequently in interviews at companies such as Google, Amazon, and Meta. They test understanding of uniform distributions, rejection sampling, and how to transform one random generator into another.
What data structure is used in Implement Rand10() Using Rand7()?
No complex data structure is required. The solution relies on mathematical mapping and randomized sampling. Only a few integer variables are used to store intermediate results from rand7() calls.
What is the time complexity of Implement Rand10() Using Rand7()?
The expected time complexity is O(1). Each attempt uses two calls to rand7(), and about 40 out of 49 generated values are accepted. Because the probability of rejection is low, the expected number of retries stays constant.