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: 


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()?

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;
}
}