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

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

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: