# 470. Implement Rand10() Using Rand7()

Given a function `rand7` which generates a uniform random integer in the range 1 to 7, write a function `rand10` which generates a uniform random integer in the range 1 to 10.

Do NOT use system’s `Math.random()`.

Example 1:

``````Input: 1
Output: [7]
``````

Example 2:

``````Input: 2
Output: [8,4]
``````

Example 3:

``````Input: 3
Output: [8,1,10]
``````

Note:

1. `rand7` is predefined.
2. Each testcase has one argument: `n`, the number of times that `rand10` is called.

1. What is the expected value for the number of calls to `rand7()` function?
2. Could you minimize the number of calls to `rand7()`?

``````rand2() - 1 + rand()2  =   ?
1            1          1
1            2          2
2            1          2
2            2          3
``````

``````（rand2() - 1） * 2 + rand()2  =   ?
1                  1         1
1                  2         2
2                  1         3
2                  2         4
``````

``````rand4() % 2 + 1 =  ?
1               2
2               1
3               2
4               1
``````

`````` rand6() % 2 + 1 =  ?
1               2
2               1
3               2
4               1
5               2
6               1
``````

``````class Solution {
public:
int rand10() {
while (true) {
int num = (rand7() - 1) * 7 + rand7();
if (num <= 40) return num % 10 + 1;
}
}
};
``````

``````class Solution {
public:
int rand10() {
int num = (rand7() - 1) * 7 + rand7();
return (num <= 40) ? (num % 10 + 1) : rand10();
}
};
``````

``````class Solution {
public:
int rand10() {
while (true) {
int a = rand7(), b = rand7();
int num = (a - 1) * 7 + b;
if (num <= 40) return num % 10 + 1;
a = num - 40, b = rand7();
num = (a - 1) * 7 + b;
if (num <= 60) return num % 10 + 1;
a = num - 60, b = rand7();
num = (a - 1) * 7 + b;
if (num <= 20) return num % 10 + 1;
}
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/470

Generate Random Point in a Circle

https://leetcode.com/problems/implement-rand10-using-rand7/

https://leetcode.com/problems/implement-rand10-using-rand7/discuss/152282/C%2B%2B-2-line

https://leetcode.com/problems/implement-rand10-using-rand7/discuss/175450/Java-Solution-explain-this-problem-with-2D-matrix

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation