470. Implement Rand10() Using Rand7() (Medium)
https://leetcode.com/problems/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:
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()
?
Solutions
class Solution extends SolBase {
public int rand10() {
int row;
int col;
int idx;
do {
row = rand7();
col = rand7();
// The probability of getting 1,2,...49 are same, be aware that 50 is not present.
// And the random data set is not integer multiple of 10, which result in the unrandom
// sequence after executing below statement.
// The workaround is to keep a set of which the size is integer multiple of 10,
// say [1~10], [1~20], [1~30], [1~40], [20~30], [20~40], [30~40], the best option is [1~40]
// since it carries the largest probability that 40/49 chance the data will locate in this
// range and the loop times will be minimized.
idx = col + (row - 1) * 7;
} while (idx > 40);
return 1 + (idx - 1) % 10;
}
}