##### Welcome to Subscribe On Youtube

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.

• /**
* 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;
}
}

• // 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();
}
};

• # 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
"""
return self.rand40() % 10 + 1

def rand49(self):
"""
random integer in 0 ~ 48
"""
return 7 * (rand7() - 1) + rand7() - 1

def rand40(self):
"""
random integer in 0 ~ 40
"""
num = self.rand49()
while num >= 40:
num = self.rand49()
return num