How do you solve Implement Rand10() Using Rand7() on LeetCode?

Implement Rand10() Using Rand7() (LeetCode #470) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Using multiple calls to rand7() can help expand the range of numbers we can generate.

What is the brute force solution for Implement Rand10() Using Rand7()?

The brute force approach for Implement Rand10() Using Rand7() is Brute Force, with O(n²) time complexity and O(1) space complexity. The simplest way to generate a number from 1 to 10 using rand7() is to repeatedly call it and map the results. However, this can lead to inefficiencies and wasted calls. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Implement Rand10() Using Rand7()?

Implement Rand10() Using Rand7() uses the following concepts: Math, Rejection Sampling, Randomized, Probability and Statistics. The recommended patterns to study are: Rejection Sampling, Randomized Algorithms.

What are the interview tips for Implement Rand10() Using Rand7()?

Always explain your thought process clearly when discussing randomization techniques. Be prepared to discuss the expected number of calls to rand7() and how to minimize them. Practice rejection sampling problems to get comfortable with the concept.

What are common mistakes when solving Implement Rand10() Using Rand7()?

Not considering the distribution of numbers generated and how to map them correctly. Failing to handle cases where the generated number exceeds the desired range.

#470

Implement Rand10() Using Rand7()

Medium

MathRejection SamplingRandomizedProbability and StatisticsRejection SamplingRandomized Algorithms

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

To minimize calls to rand7(), we can use a rejection sampling technique that allows us to generate numbers uniformly from 1 to 10 without excessive calls.

⚙️

Algorithm

3 steps

1Step 1: Call rand7() twice to generate a number in the range [1, 49].
2Step 2: Map this number to a number between 1 and 10. If the number is greater than 40, discard it and repeat.
3Step 3: Return the mapped number.

solution.py7 lines

1def rand7(): ... # Assume this is provided
2
3def rand10():
4    while True:
5        num = (rand7() - 1) * 7 + rand7()  # Generates a number from 1 to 49
6        if num <= 40:
7            return (num - 1) % 10 + 1

ℹ

Complexity note: This approach has a time complexity of O(n) on average because we are more likely to get a valid number with fewer calls to rand7(). The rejection sampling reduces the number of calls significantly.

1Using multiple calls to rand7() can help expand the range of numbers we can generate.
2Rejection sampling is an effective technique to ensure uniform distribution while minimizing unnecessary calls.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.