> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/math/sui-ji-shu/470.-implement-rand10-using-rand7.md).

# 470. Implement Rand10() Using Rand7()

给定一个服从uniform distribution的范围为\[1, 7]随机数生成器，让实现一个\[1, 10]的随机数生成器。等概率可以看成有\[1, 7]有相同数目的格子，现在要利用它做出\[1, 10]每个元素有相同数目的格子。[花花](https://link.zhihu.com/?target=https%3A//www.youtube.com/watch%3Fv%3DOQi4n8EKRD8)讲的非常好，这里直接用它的图了:![](https://pic4.zhimg.com/80/v2-c565fddf83b20acdcde0bf3bcc691753_hd.jpg)

思想如图，调用两次rand7，横竖生成一个矩阵，相当于生成49个等概率的格子，然后每十个一切，前40个看成一个整体，能保证落在前40个\[1, 10]都是等概率的(即相同数目个1, 2, 3, ...,10)。如果落在了后面9个格子，相当于这次作废，重头采样。这个思想叫做Rejection Sampling。

```cpp
/*
 * @lc app=leetcode id=470 lang=cpp
 *
 * [470] Implement Rand10() Using Rand7()
 */
// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
    int rand10() {
        int index = INT_MAX;
        while (index >= 40) {
            index = 7 * (rand7() - 1) + (rand7() - 1);
        }   
        return index % 10 + 1;
    }
};


```