Why can't I just use rand7() % 10 to implement rand10()?

Using rand7() % 10 introduces bias because 7 is not divisible by 10, which prevents uniform distribution of outputs.

How does rejection sampling ensure uniform randomness in rand10()?

Rejection sampling discards out-of-range values that would skew probabilities, only accepting values that map evenly to 1-10.

Can the rand10() implementation handle large n efficiently?

Yes, by reusing out-of-range values from previous iterations, the expected number of rand7() calls per rand10() remains low, even for large n.

Is it possible to minimize retries when using rand7() to create rand10()?

Yes, optimizing the transformation of leftover values reduces unnecessary retries, improving efficiency without affecting uniformity.

What pattern does 'Implement Rand10() Using Rand7()' mainly test?

It tests the Math plus Rejection Sampling pattern, requiring careful mapping of a smaller uniform distribution to a larger one without bias.

#470

Medium

auto_awesome数学·结合·rejection·sampling

LeetCode 题解工作台

用 Rand7() 实现 Rand10()

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。每个测试用例将有一个内部参数 n ，即你实现的函数 rand1…

数学拒绝采样随机化概率与统计

题目描述

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。

每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

示例 1:

输入: 1
输出: [2]

示例 2:

输入: 2
输出: [2,8]

示例 3:

输入: 3
输出: [3,8,10]

提示:

1 <= n <= 10⁵

进阶:

rand7()调用次数的期望值是多少 ?
你能否尽量少调用 rand7() ?

lightbulb

解题思路

方法一：拒绝采样

我们可以使用拒绝采样的方法实现等概率生成任意区间的随机数。拒绝采样的思路是如果生成的随机数落在我们希望的区间内，那么就返回该随机数，否则会不断生成直到生成一个落在区间内的随机数为止。

对于本题，我们可以通过调用 $rand7()$ 两次来实现生成 $[1,10]$ 以内的随机数，具体如下：

我们生成一个大于等于 $1$ 且小于等于 $40$ 的整数 $x$ ，其中等概率生成的方式为 $x = (rand7() - 1) \times 7 + rand7()$ ，然后，我们返回 $x \bmod 10 + 1$ 即可。

期望时间复杂度为 $O(1)$ ，但是最坏情况下会达到无穷大的时间复杂度。空间复杂度为 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

# 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):
        """
        :rtype: int
        """
        while 1:
            i = rand7() - 1
            j = rand7()
            x = i * 7 + j
            if x <= 40:
                return x % 10 + 1

speed

复杂度分析

指标	值
时间	complexity depends on the expected number of retries caused by rejection sampling, roughly O(1) expected per call. Space complexity is O(1) since no additional structures are needed.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Will your solution maintain uniform distribution for all outputs?
question_mark
How can you reduce the expected number of rand7() calls in your mapping?
question_mark
Explain why simple modulo of a single rand7() call is biased.

warning

常见陷阱

外企场景

error
Using rand7() % 10 directly introduces bias.
error
Failing to properly reject numbers outside the valid range.
error
Not optimizing the reuse of out-of-range values, causing inefficiency.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implement randN() using randM() for arbitrary N > M with rejection sampling.
arrow_right_alt
Generate a random number in a non-continuous range using rand7().
arrow_right_alt
Extend rand10() implementation to return multiple outputs efficiently for large n.

help

常见问题

外企场景

继续练习

#478 在圆内随机生成点 #497 非重叠矩形中的随机点 #519 随机翻转矩阵