LeetCode 470: Implement Rand10() Using Rand7() Solution in Python – A Step-by-Step Guide

What Is LeetCode 470: Implement Rand10() Using Rand7()?

In LeetCode 470: Implement Rand10() Using Rand7(), you’re given a function rand7() that generates integers 1 to 7 uniformly, and your task is to implement rand10() to generate integers 1 to 10 uniformly using only rand7() calls. For example, you might roll rand7() twice to get a bigger range, then map it fairly to 1-10. It’s like turning a seven-note tune into a ten-note melody without missing a beat.

Problem Statement

• Input: None (uses rand7() internally).
• Output: int—random number from 1 to 10, uniformly distributed.
• Rules:
• Use only rand7() to generate randomness.
• Ensure uniform distribution (each number 1-10 has a 1/10 chance).
• Minimize expected calls to rand7().

Constraints

• rand7() generates 1 to 7 uniformly.
• At most 10^5 calls to rand10() in testing.

Examples to Get Us Started

• Input: Call rand10().
• Output: Any number from 1 to 10 (e.g., 3, 7, 10), each with 10% chance.
• Input: Multiple calls to rand10().
• Output: Sequence like [4, 8, 1, 10, 6], uniform over many calls.

Understanding the Problem: Rolling a Bigger Die

To solve LeetCode 470: Implement Rand10() Using Rand7() in Python, we need to transform a uniform random generator from 1-7 into one for 1-10, ensuring each number has an equal 1/10 chance. A naive approach—rolling rand7() and capping at 10—won’t work (it’s biased toward 1-7). The key? Use multiple rand7() calls to create a larger range, then apply rejection sampling to map it uniformly to 10 outcomes. We’ll explore:

• Best Solution (Rejection Sampling with Base Conversion): O(1) expected time, O(1) space—fast and optimal.
• Alternative Solution (Simple Rejection Sampling): O(1) expected time, O(1) space—simpler but less efficient.

Let’s dive into the best solution—it’s the dice-rolling masterstroke we need.

Best Solution: Rejection Sampling with Base Conversion

Why This Is the Best Solution

The rejection sampling with base conversion approach is the top pick because it achieves O(1) expected time and O(1) space, minimizing rand7() calls by generating a range of at least 40 (7 * 7 = 49 > 40) and rejecting excess values to map uniformly to 1-10. It uses two rand7() calls to create a 2-digit base-7 number, then scales it down efficiently. It’s like rolling two seven-sided dice to get a big enough canvas, then painting exactly 10 colors—smart and streamlined!

How It Works

Here’s the strategy:

• Step 1: Call rand7() twice:
• First call (idx) = 1-7.
• Second call (col) = 1-7.
• Step 2: Compute a number in range 0-48:
• val = (idx - 1) * 7 + (col - 1).
• Step 3: Rejection sampling:
• If val < 40, use it (40 = 10 * 4, maps to 0-9).
• If val ≥ 40, reject and retry.
• Step 4: Return val % 10 + 1 (maps 0-39 to 1-10).
• Why It Works:
• 49 outcomes (7 * 7), 40 used (4 sets of 10).
• Rejection ensures uniform 1/10 probability per number.
• Expected calls ≈ 2.45 (49/40 retries).

Step-by-Step Example

Example: Simulate rand10()

• Roll 1: idx = 3 (rand7() = 3).
• Roll 2: col = 5 (rand7() = 5).
• Compute: val = (3-1) * 7 + (5-1) = 2 * 7 + 4 = 18.
• Check: 18 < 40, accept.
• Map: 18 % 10 + 1 = 8 + 1 = 9.
• Result: 9.

Example: Rejection Case

• Roll 1: idx = 7, col = 7.
• Compute: val = (7-1) * 7 + (7-1) = 6 * 7 + 6 = 42.
• Check: 42 ≥ 40, reject, retry.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy code# 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:
            # Step 1: Two rand7() calls
            idx = rand7()  # 1-7
            col = rand7()  # 1-7

            # Step 2: Compute value in 0-48
            val = (idx - 1) * 7 + (col - 1)  # 0 to 48

            # Step 3: Rejection sampling
            if val < 40:  # Use 0-39
                # Step 4: Map to 1-10
                return val % 10 + 1
            # Else retry

• Line 8-10: Call rand7() twice for idx and col.
• Line 13: Compute val = (idx-1)*7 + (col-1) (e.g., 0-48).
• Line 16-18: If val < 40, map to 1-10; else retry.
• Time Complexity: O(1) expected—avg 2.45 calls (49/40 rejection rate).
• Space Complexity: O(1)—few variables.

It’s like a dice-rolling wizard!

Alternative Solution: Simple Rejection Sampling

Why an Alternative Approach?

The simple rejection sampling method uses one rand7() call—O(1) expected time, O(1) space—rejecting values > 5 to map to 1-5, then scaling with a second call. It’s less efficient (more rejections) but intuitive, like rolling until you get a usable number. Good for simplicity or learning!

How It Works

• Step 1: Call rand7(), reject if > 5, get 0-4.
• Step 2: Call rand7() again, add 5 if second roll ≤ 5.
• Step 3: Return mapped value (1-10).

Step-by-Step Example

Example: Simulate rand10()

• Roll 1: 6 > 5, retry → 4 ≤ 5, val = 4-1 = 3.
• Roll 2: 3 ≤ 5, val = 3 + 0 = 3.
• Map: 3 + 1 = 4.
• Result: 4.

Code for Simple Rejection

Copy codeclass Solution:
    def rand10(self) -> int:
        while True:
            val = rand7()
            if val <= 5:
                break
        while True:
            offset = rand7()
            if offset <= 5:
                return val + (0 if offset <= 3 else 5)
        return val  # Fallback (won't reach due to loops)

• Line 4-6: Get val ≤ 5.
• Line 7-10: Get offset ≤ 5, map to 1-5 or 6-10.
• Time Complexity: O(1) expected—higher rejection rate.
• Space Complexity: O(1)—minimal.

It’s a basic dice roller!

Comparing the Two Solutions

• Base Conversion (Best):
• Pros: O(1), fewer expected calls (~2.45).
• Cons: Slightly more math.
• Simple Rejection (Alternative):
• Pros: O(1), simpler logic.
• Cons: More calls (~2.8 avg).

Base conversion wins for efficiency.

Edge Cases and Examples

• Single Call: Uniform 1-10 output.
• Multiple Calls: Consistent distribution.
• Rejection: Handles all rand7() outputs.

Base conversion handles all perfectly.

Complexity Recap

• Base Conversion: Expected Time O(1) (~2.45 calls), Space O(1).
• Simple Rejection: Expected Time O(1) (~2.8 calls), Space O(1).

Base conversion’s the champ.

Key Takeaways

• Base Conversion: Maximize range, minimize waste.
• Simple Rejection: Easy but less optimal.
• Python Tip: Randomness bends—see [Python Basics](/python/basics).

Final Thoughts: Roll That Ten

LeetCode 470: Implement Rand10() Using Rand7() in Python is a probabilistic dice-rolling adventure. Base conversion is your fast roller, while simple rejection is a steady tosser. Want more randomness? Try LeetCode 384: Shuffle an Array or LeetCode 528: Random Pick with Weight. Ready to roll some tens? Head to Solve LeetCode 470 on LeetCode and spin it today—your coding skills are dice-ready!