LeetCode 470: Implement Rand10() Using Rand7()

Problem Restatement

We are given an API:

rand7()

It returns a uniformly random integer from 1 to 7.

We need to implement:

rand10()

It must return a uniformly random integer from 1 to 10.

We may only call rand7(). We should not use any other random API. The official problem asks for a uniform random integer in [1, 10] using only rand7().

Input and Output

Item	Meaning
Given API	rand7()
rand7() output	Uniform integer from 1 to 7
Function to implement	rand10()
rand10() output	Uniform integer from 1 to 10
Restriction	Only call rand7()

Function shape:

class Solution:
    def rand10(self) -> int:
        ...

Examples

The test system may call rand10() many times.

Example outputs may look like:

[2]
[2, 8]
[3, 8, 10]

These are only sample random outputs.

The important requirement is not a fixed output sequence.

The important requirement is that each number from 1 to 10 has equal probability.

First Thought: Use One rand7() Call

A first idea might be:

return rand7()

This can only produce numbers from 1 to 7.

It never produces:

8, 9, 10

So it cannot be correct.

Another idea is to scale the result somehow, but scaling 1..7 into 1..10 creates uneven probabilities because 7 outcomes cannot be divided evenly into 10 outcomes.

We need a larger uniform sample space.

Problem With Direct Mapping

A uniform random generator with 7 outcomes cannot directly produce 10 equally likely outcomes.

To map outcomes evenly, the number of source outcomes must be divisible by the number of target outcomes.

But:

7 % 10 != 0

So one call is not enough.

If we call rand7() twice, we get:

7 * 7 = 49

equally likely outcomes.

Now we can use 40 of them because:

40 % 10 == 0

The remaining 9 outcomes are rejected and retried.

Key Insight

Two calls to rand7() can generate a uniform number from 1 to 49.

Think of the first call as a row and the second call as a column in a 7 x 7 grid.

row = rand7() - 1   # 0 to 6
col = rand7()       # 1 to 7
x = row * 7 + col   # 1 to 49

Every value from 1 to 49 is equally likely.

Now accept only values from 1 to 40.

Since 40 is divisible by 10, each result from 1 to 10 can receive exactly 4 source values.

Then map:

1..40 -> 1..10

using:

(x - 1) % 10 + 1

or equivalently for x <= 40:

x % 10 + 1

Both are uniform, but (x - 1) % 10 + 1 is easier to reason about.

Algorithm

Repeat forever:

1. Call rand7() twice.
2. Convert the two calls into a number x from 1 to 49.
3. If x <= 40, return (x - 1) % 10 + 1.
4. Otherwise, reject x and try again.

The loop eventually returns with probability 1.

The chance of accepting on each attempt is:

40 / 49

So the expected number of attempts is:

49 / 40

That is close to 1.

Walkthrough

Suppose:

rand7() -> 3
rand7() -> 5

Then:

row = 3 - 1 = 2
col = 5
x = 2 * 7 + 5 = 19

Since 19 <= 40, accept it.

Map it to 1..10:

(19 - 1) % 10 + 1 = 9

So this call returns:

9

If instead:

x = 42

then 42 > 40, so we reject it and call rand7() twice again.

Correctness

Each call to rand7() is uniform over 1..7.

Two independent calls create 49 equally likely ordered pairs.

The formula:

x = (rand7() - 1) * 7 + rand7()

maps those ordered pairs one-to-one onto the integers from 1 to 49.

So x is uniform over 1..49.

The algorithm accepts only 1..40. Since the original distribution is uniform, the accepted value is uniform over 1..40.

The mapping:

(x - 1) % 10 + 1

maps the 40 accepted values onto 1..10, with exactly 4 accepted values per output.

Therefore, each number from 1 to 10 has the same probability.

So rand10() is uniform.

Complexity

Metric	Value	Why
Expected time	O(1)	Each attempt succeeds with probability 40 / 49
Worst-case time	Unbounded	Rejection sampling can theoretically reject forever
Space	O(1)	Only a few variables are used

The probability of many consecutive rejections decreases exponentially.

Implementation

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

class Solution:
    def rand10(self) -> int:
        while True:
            row = rand7() - 1
            col = rand7()
            x = row * 7 + col

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

Code Explanation

The first call gives a zero-based row:

row = rand7() - 1

So row is from 0 to 6.

The second call gives a one-based column:

col = rand7()

So col is from 1 to 7.

Together:

x = row * 7 + col

creates a uniform value from 1 to 49.

If x is at most 40, we can use it:

if x <= 40:

Then:

return (x - 1) % 10 + 1

maps it uniformly to 1..10.

If x is 41..49, the loop repeats.

Alternative Implementation

Some solutions use a zero-based number from 0 to 48.

class Solution:
    def rand10(self) -> int:
        while True:
            x = (rand7() - 1) * 7 + (rand7() - 1)

            if x < 40:
                return x % 10 + 1

Here, x is uniform from 0 to 48.

We accept 0..39.

That also gives 40 equally likely values, which map evenly to 1..10.

Testing

True randomness cannot be tested with exact equality.

Instead, we test two things:

1. Every output is in the range 1..10.
2. Over many calls, the counts are roughly balanced.

Example local simulation:

import random
from collections import Counter

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

class Solution:
    def rand10(self) -> int:
        while True:
            row = rand7() - 1
            col = rand7()
            x = row * 7 + col

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

def run_tests():
    s = Solution()
    counts = Counter()

    trials = 100_000

    for _ in range(trials):
        value = s.rand10()
        assert 1 <= value <= 10
        counts[value] += 1

    print(counts)

run_tests()

Test meaning:

Test	Why
Range check	Confirms rand10() only returns 1..10
Large sample count	Helps detect obvious bias
Rejection path	Values 41..49 should retry, not map directly
Uniformity reasoning	Proven by construction, not by exact sample counts