Implement Rand10 Using Rand7: Rejection Sampling

LeetCode Implement Rand10() Using Rand7() (problem 470) asks you to write a function rand10() that returns a uniform random integer from 1 to 10, using only a given rand7() function that returns a uniform random integer from 1 to 7.

You cannot just call rand7() once and take the result modulo 10. That would not give you a uniform distribution over 1-10. The trick is to combine multiple rand7() calls to build a larger uniform range, then carve out a piece that divides evenly into 10.

The problem

Given a function rand7() that returns each integer from 1 to 7 with equal probability, implement a function rand10() that returns each integer from 1 to 10 with equal probability. You may call rand7() as many times as you want.

Why this problem matters

This problem teaches rejection sampling, a technique used across probability, statistics, and systems design. The core idea is: if you cannot generate exactly the distribution you want, generate a larger uniform distribution and throw away the values that do not fit.

Rejection sampling shows up any time you need to convert one source of randomness into another. If you have a coin and need a die, or a 6-sided die and need a 10-sided die, the same principle applies. Understanding this pattern helps you reason about randomness, fairness, and expected running time in real systems.

The key insight

Call rand7() twice. The first call picks a row (1-7) and the second picks a column (1-7). That gives you a uniform random number from a 7x7 grid of 49 outcomes. You can map this pair to a single index using the formula idx = (row - 1) * 7 + col, which produces values from 1 to 49, each with probability 1/49.

Now, 49 does not divide evenly by 10, so you cannot map all 49 values to 10 outcomes with equal weight. But 40 does divide evenly by 10. So you accept values from 1 to 40 and reject values from 41 to 49. When a value is rejected, you simply try again.

For accepted values, the mapping is: result = (idx - 1) % 10 + 1. Since there are exactly 4 values in 1-40 that map to each result in 1-10, every outcome has the same probability.

The code

def rand10():
    while True:
        row = rand7()
        col = rand7()
        idx = (row - 1) * 7 + col  # uniform in [1, 49]
        if idx <= 40:
            return (idx - 1) % 10 + 1

That is the entire solution. The while True loop handles rejection: if idx lands in 41-49, you discard the result and roll again. If idx is in 1-40, you map it to 1-10 and return.

Why this works

Each pair (row, col) has probability 1/49. There are 49 possible pairs, and they are all equally likely because the two rand7() calls are independent.

Of those 49 outcomes, 40 land in the acceptance zone. For each value k in 1-10, exactly 4 of the 40 accepted indices map to k. So the probability of returning k, conditional on acceptance, is 4/40 = 1/10 for every k. That is exactly the uniform distribution you need.

The rejection step does not introduce bias. When you reject and retry, you are starting fresh with two new independent rand7() calls. The conditional probability of any accepted outcome remains uniform.

Visual walkthrough

The probability of acceptance on any single attempt is 40/49, which is about 81.6%. That means on average you need 49/40 = 1.225 iterations of the loop, or about 2.45 calls to rand7() per successful rand10() call.

The worst case is theoretically infinite, since you could keep landing in 41-49 forever. But the probability of needing more than k iterations is (9/49)^k, which drops extremely fast. The chance of needing more than 10 iterations is less than one in 38 million.

Complexity analysis

Each iteration takes constant time (two rand7() calls plus arithmetic). The expected number of iterations is constant (1.225). While the worst case is unbounded, the expected time is O(1). Space is O(1) since no data structures are used.

Building blocks

Rejection sampling

The core technique here is rejection sampling. You generate a candidate from a distribution you can produce (uniform over 1-49), then accept or reject it based on whether it falls in a target range (1-40). This is useful whenever you need to generate samples from a distribution that does not exactly match your source of randomness.

The key design choice is maximizing the acceptance rate. We use a 7x7 grid (49 cells) and accept the largest multiple of 10 that fits (40). That gives an acceptance rate of 40/49. You could use a 7x7x7 cube (343 cells) and accept the first 340 for a rate of 340/343, but the extra rand7() call per iteration makes the total cost similar.

Uniform distribution from independent sources

When you make two independent calls to rand7(), the pair (a, b) is uniformly distributed over all 49 combinations. The formula (a - 1) * 7 + b is a bijection from pairs to integers 1-49. This is the same principle behind converting a pair of dice rolls into a single number: if both dice are fair and independent, every pair is equally likely.

Modular arithmetic for equal partitioning

The mapping (idx - 1) % 10 + 1 partitions the integers 1-40 into 10 groups of 4. This works because 40 is an exact multiple of 10. If you tried to use all 49 values with modular arithmetic, some remainders would appear 5 times and others only 4 times, breaking uniformity.

Edge cases

• Expected retries. On average, each call to rand10() takes about 1.225 loop iterations. This is not an edge case, but it is worth knowing for interview discussions about expected complexity.
• Long retry streaks. In theory, you could get unlucky and land in 41-49 many times in a row. The probability of needing more than 20 retries is roughly (9/49)^20, which is astronomically small. For all practical purposes, the function terminates quickly.
• No special inputs. Unlike most LeetCode problems, this one has no input array or parameters. The function signature is fixed. There are no empty inputs, null checks, or boundary values to worry about.

From understanding to recall

The mental model for this problem is simple: you need 10 equally likely outcomes, but your source only gives you 7. A single rand7() call is not enough because 7 is not a multiple of 10. Two calls give you 49 outcomes, and the largest multiple of 10 inside 49 is 40. Accept 1-40, reject 41-49, and map the accepted value with modular arithmetic.

If you remember that framework, you can reconstruct the code from scratch. The formula idx = (row - 1) * 7 + col is just the standard way to flatten a 2D grid index into 1D. The mapping (idx - 1) % 10 + 1 is the standard way to cycle through 10 buckets. And the while True loop is the textbook structure for rejection sampling.

Practice writing it from memory once or twice over a few days. The logic is compact enough that it sticks quickly once you understand why each piece is there.

Related posts

• Linked List Random Node - Reservoir sampling for random selection
• Random Pick Index - Another random selection problem
• Shuffle an Array - Fisher-Yates shuffle for uniform randomness