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: [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.
-
/** * 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