LeetCode 470 - Implement Rand10() Using Rand7()

The problem provides access to a single API, rand7(), which returns a uniformly random integer from 1 to 7. The task is to implement another function, rand10(), which must return a uniformly random integer from 1 to 10.

leetcodemediummathrejection-samplingrandomizedprobability-and-statistics

LeetCode Problem 470

Difficulty: 🟡 Medium
Topics: Math, Rejection Sampling, Randomized, Probability and Statistics

Solution

Problem Understanding

The problem provides access to a single API, rand7(), which returns a uniformly random integer from 1 to 7. The task is to implement another function, rand10(), which must return a uniformly random integer from 1 to 10.

The important constraint is that we are not allowed to use any built-in random number generators. Every piece of randomness must ultimately come from repeated calls to rand7().

The challenge is not simply generating numbers in the range [1, 10]. The difficult part is ensuring that every number from 1 through 10 has exactly the same probability of being chosen. A naive implementation can easily introduce bias.

The hidden parameter n in the test cases only indicates how many times the online judge will call rand10(). It is not passed directly into the function and does not affect the implementation logic.

Because n can be as large as 10^5, the solution must be efficient. A poor implementation that repeatedly retries too often could become unnecessarily slow.

A major observation is that 7 does not divide evenly into 10, which means we cannot simply map one call to rand7() directly into one result from 1 to 10. For example, using something like:

return rand7() % 10 + 1

would never generate values greater than 8. Similarly, combining multiple calls incorrectly can make some outputs more likely than others.

The problem guarantees that rand7() itself is perfectly uniform, meaning each value from 1 through 7 occurs with probability 1/7. Our implementation must preserve uniformity while transforming the output space from size 7 into size 10.

Important edge cases include situations where the generated intermediate random value does not map evenly into [1, 10]. A naive implementation might incorrectly compress ranges and create probability bias. The correct solution must explicitly reject invalid ranges to maintain equal probability.

Approaches

Brute Force Approach

A brute force idea is to repeatedly call rand7() and try to directly map its outputs into the range [1, 10]. One attempt could be to combine two calls:

(rand7() + rand7()) % 10 + 1

This does produce numbers from 1 to 10, but the distribution is not uniform. Some sums occur more frequently than others. For example, the sum 2 can only occur one way, while the sum 8 can occur many different ways.

Another brute force attempt is to keep generating numbers until we somehow land in the desired range. However, without careful probability management, this still introduces uneven probabilities.

The brute force approach fails because it ignores a critical requirement: every output must have identical probability.

Key Insight

The key insight is that two independent calls to rand7() can generate a uniform distribution over 49 equally likely outcomes.

Since:

7 × 7 = 49

we can think of the pair (a, b) as representing numbers from 1 to 49.

Because 49 is larger than 10, we can use rejection sampling. Specifically:

  • Use the first 40 values because 40 is divisible by 10
  • Reject values 41 through 49
  • Map the remaining values evenly into 1 through 10

This works because each of the 40 accepted states occurs with equal probability.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(1) O(1) Produces biased probabilities, therefore incorrect
Optimal O(1) expected O(1) Uses rejection sampling to guarantee uniform distribution

Algorithm Walkthrough

  1. Call rand7() twice to generate two independent random values.

Let:

row = rand7()
col = rand7()

Since each call is independent and uniformly distributed, every pair (row, col) is equally likely. 2. Convert the two-dimensional pair into a single number from 1 to 49.

We use:

index = (row - 1) * 7 + col

This effectively lays out all possible pairs in a 7 × 7 grid.

For example:

row col index
1 1 1
1 7 7
2 1 8
7 7 49
3. Check whether the generated number falls within the usable range.

We only accept values from 1 through 40.

Why 40?

Because:

40 = 10 × 4

This means every output from 1 to 10 can appear exactly four times. 4. Reject invalid values.

If the generated value is between 41 and 49, discard it and repeat the process.

This is the core idea behind rejection sampling. 5. Convert the accepted value into the final answer.

Once we have a valid number from 1 to 40, map it into [1, 10] using:

result = (index - 1) % 10 + 1

This evenly distributes the outcomes.

Why it works

Each pair of rand7() calls produces one of 49 equally likely outcomes. By rejecting values 41 through 49, we are left with 40 equally likely outcomes. Since 40 divides evenly into 10, each final value from 1 through 10 appears exactly four times. Therefore, the probability distribution is perfectly uniform.

Python Solution

# The rand7() API is already defined for you.
# def rand7():
#     # returns a random integer in the range 1 to 7

class Solution:
    def rand10(self) -> int:
        while True:
            row = rand7()
            col = rand7()

            index = (row - 1) * 7 + col

            if index <= 40:
                return (index - 1) % 10 + 1

The implementation continuously generates candidate values until a valid one is found.

The variables row and col represent two independent random values from 1 to 7. These are combined into a single uniformly distributed value from 1 to 49.

The expression:

(row - 1) * 7 + col

maps the 7 × 7 grid into a linear sequence.

The condition:

if index <= 40:

implements rejection sampling. Values above 40 are discarded because they would create uneven probabilities.

Finally, modulo arithmetic converts the accepted range into values from 1 to 10.

Go Solution

func rand10() int {
    for {
        row := rand7()
        col := rand7()

        index := (row-1)*7 + col

        if index <= 40 {
            return (index-1)%10 + 1
        }
    }
}

The Go implementation follows exactly the same logic as the Python version.

Go uses explicit variable declarations with :=. Since integers in this problem remain very small, integer overflow is not a concern.

The infinite for loop is the Go equivalent of Python's while True: loop.

Worked Examples

Example 1

Input: n = 1
Possible Output: [2]

Suppose the following calls occur:

Step rand7() #1 rand7() #2 index Accepted? Final Result
1 1 2 2 Yes 2

Calculation:

index = (1 - 1) * 7 + 2
      = 2

result = (2 - 1) % 10 + 1
       = 2

Example 2

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

First call to rand10():

Step rand7() #1 rand7() #2 index Accepted? Result
1 1 2 2 Yes 2

Second call to rand10():

Step rand7() #1 rand7() #2 index Accepted? Result
1 2 1 8 Yes 8

Calculation:

index = (2 - 1) * 7 + 1
      = 8

result = (8 - 1) % 10 + 1
       = 8

Example 3

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

Third generated value:

Step rand7() #1 rand7() #2 index Accepted? Result
1 2 3 10 Yes 10

Calculation:

index = (2 - 1) * 7 + 3
      = 10

result = (10 - 1) % 10 + 1
       = 10

Example Showing Rejection

Suppose:

Step rand7() #1 rand7() #2 index Accepted?
1 6 7 42 No
2 2 5 12 Yes

The first generated value is rejected because 42 > 40.

The algorithm retries until a valid value is produced.

Complexity Analysis

Measure Complexity Explanation
Time O(1) expected Rejection sampling retries only occasionally
Space O(1) Uses only a few integer variables

The algorithm has constant expected time complexity because each attempt succeeds with probability:

40 / 49

The expected number of attempts is therefore:

49 / 40

Since each attempt uses two calls to rand7(), the expected number of rand7() calls is:

2 × (49 / 40) = 2.45

This remains constant regardless of input size.

Test Cases

# Mock rand7 implementation for testing purposes only

from collections import Counter
import random

def rand7():
    return random.randint(1, 7)

class Solution:
    def rand10(self) -> int:
        while True:
            row = rand7()
            col = rand7()

            index = (row - 1) * 7 + col

            if index <= 40:
                return (index - 1) % 10 + 1

sol = Solution()

# Test 1: output always within valid range
for _ in range(1000):
    value = sol.rand10()
    assert 1 <= value <= 10  # verifies range correctness

# Test 2: every number appears eventually
results = [sol.rand10() for _ in range(10000)]
counts = Counter(results)

for num in range(1, 11):
    assert num in counts  # verifies all outputs are reachable

# Test 3: approximate uniformity
# each number should appear reasonably often
for count in counts.values():
    assert count > 700  # rough lower bound for randomness sanity

# Test 4: repeated calls do not crash
for _ in range(100000):
    sol.rand10()  # stress test for stability

# Test 5: verify no invalid values produced
results = [sol.rand10() for _ in range(5000)]
assert all(1 <= x <= 10 for x in results)  # boundary validation
Test Why
Generate 1000 values Verifies all outputs remain within [1, 10]
Check all numbers appear Ensures every value is reachable
Approximate uniformity test Validates probability distribution is reasonably balanced
Stress test with 100000 calls Confirms stability under heavy usage
Boundary validation Ensures no invalid outputs are produced

Edge Cases

One important edge case occurs when the generated intermediate value falls between 41 and 49. These values cannot be evenly mapped into 1 through 10. A buggy implementation might still apply modulo arithmetic directly, which would make some outputs more likely than others. The rejection sampling step prevents this by discarding those values entirely.

Another important case is repeated rejection. In theory, the algorithm could repeatedly generate invalid values. A poor implementation might accidentally enter an infinite loop because of incorrect retry logic. This implementation handles retries safely using a simple infinite loop that continues until a valid value is produced.

A third edge case involves incorrect index construction. If the formula converting two rand7() calls into a value from 1 to 49 is wrong, some numbers may become unreachable or duplicated. The expression:

(row - 1) * 7 + col

guarantees that every value from 1 through 49 appears exactly once, preserving uniform probability across the entire space.