Implement Rand10() Using Rand7()
Problem
Given the API rand7() — uniform integers in 1..7 — write rand10() that returns a uniform integer in 1..10. You may call rand7() any number of times, but cannot use any other randomness source.
rand7() returns 5, 3 (then 2, 7 ...)rand10() returns 9 (then a fresh call returns 2 ...)def rand10():
while True:
row = rand7()
col = rand7()
idx = (row - 1) * 7 + col # 1..49
if idx <= 40:
return ((idx - 1) % 10) + 1function rand10() {
while (true) {
const row = rand7();
const col = rand7();
const idx = (row - 1) * 7 + col; // 1..49
if (idx <= 40) return ((idx - 1) % 10) + 1;
}
}class Solution extends SolBase {
public int rand10() {
while (true) {
int row = rand7();
int col = rand7();
int idx = (row - 1) * 7 + col;
if (idx <= 40) return ((idx - 1) % 10) + 1;
}
}
}class Solution : public SolBase {
public:
int rand10() {
while (true) {
int row = rand7();
int col = rand7();
int idx = (row - 1) * 7 + col;
if (idx <= 40) return ((idx - 1) % 10) + 1;
}
}
};Explanation
We only have a die that gives 1..7, but we need a fair 1..10. The trick is to combine two rolls into a fair number in a bigger range, then keep only the part that divides evenly by 10 — this is called rejection sampling.
Two rolls of rand7() give a pair (row, col), and idx = (row - 1) * 7 + col turns that pair into a uniform number from 1 to 49. Every one of the 49 outcomes is equally likely.
The problem is 49 is not a multiple of 10. So we accept only when idx <= 40 and reject and retry otherwise. The 40 accepted values split cleanly into 10 groups of 4, so ((idx - 1) % 10) + 1 gives a perfectly fair number in 1..10.
Example: rolls 5 and 3 give idx = (5-1)*7 + 3 = 31, which is ≤ 40, so we accept and return ((31-1) % 10) + 1 = 1. If instead the rolls gave idx = 45, we throw it away and roll again.
Because we accept 40 out of every 49 attempts, each call usually succeeds on the first try, giving expected O(1) time even though the worst case loops a few times.