Formatted question description: https://leetcode.ca/all/470.html
470. Implement Rand10() Using Rand7() (Medium)
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:
rand7
is predefined.- Each testcase has one argument:
n
, the number of times thatrand10
is called.
Follow up:
- What is the expected value for the number of calls to
rand7()
function? - Could you minimize the number of calls to
rand7()
?
Related Topics:
Random, Rejection Sampling
Solution 1.
// OJ: https://leetcode.com/problems/implement-rand10-using-rand7/
// Time: O(1) on average, O(Infinity) in worst case
// Space: O(1)
class Solution {
int rand2() {
while (true) {
int r = rand7();
if (r <= 6) return 1 + (r >= 4);
}
}
int rand5() {
while (true) {
int r = rand7();
if (r <= 5) return r;
}
}
public:
int rand10() {
return (rand2() - 1) * 5 + rand5();
}
};
Solution 2. Rejection Sampling
// OJ: https://leetcode.com/problems/implement-rand10-using-rand7/solution/
// Time: O(1) on average, O(Infinity) in worst case
// Space: O(1)
// Ref: https://leetcode.com/problems/implement-rand10-using-rand7/solution/
class Solution {
public:
int rand10() {
while (true) {
int r = (rand7() - 1) * 7 + rand7(); // generate evenly distributed [1, 49].
if (r <= 40) return r % 10 + 1; // Only accept numbers in range [1, 40]
}
}
};
Java
/**
* The rand7() API is already defined in the parent class SolBase.
* public int rand7();
* @return a random integer in the range 1 to 7
*/
class Solution extends SolBase {
public int rand10() {
int num = 100;
while (num >= 40) {
int num1 = rand7() - 1;
int num2 = rand7() - 1;
num = num1 * 7 + num2;
}
int randNum = num / 4 + 1;
return randNum;
}
}