Big to small

If we have a api rand10 which generate random values from [1,10], then how could we use this api to build an api rand7 which generates random values from [0,7]?

This solution is to use rejection sampling. The main idea is when you generate a number in the desired range, output that number immediately. If the number is out of the desired range, reject it and re-sample again. Because each call of rand10 should get a result with equal probability, if we get a value bigger than 7, we just roll the dice again, until we get a valid result.

// if we already have rand10
function rand7() {
    const v = rand10();
    if (v <= 7) return v;
    else return rand7(); // roll the dice again
}

Small to big

Now how about simluate big rand by small rand? Say we have an api rand7, how to build an api rand10?

The idea is, we can make this happen by rolling the dice many times. So if we run the rand7 twice, we should get a result table like below.

  1  2  3  4  5  6  7
1 a  b  c  d  e  f  g
2 h  i  ...
3
4
5
6
7

So each table cell stands for a possible result. Each table cell should have the same possibilities. Now we have 49 cells, so we have rand49.

Implement Rand10() Using Rand7()

Now with all the above information, let's solve the leetcode Implement Rand10() Using Rand7() problem.

The problem is to implement big rand by small rand. So the solution is, first make the rand bigger, then choose the valid result.

// if we already have rand7
function rand10(): number {
    const row = rand7();
    const col = rand7();

    // cell index in the table
    const idx = col + (row-1) * 7

    if (idx <= 10) {
        return idx;
    } else {
        rand10();
    }
};