題目： LeetCode - 470. Implement Rand10() Using Rand7()

題目說明

給一個 rand7() 會隨機回傳 1 ~ 7 整數的函式 ( 機率相等 )，要求完成 rand10()。題目要求不要使用函式庫的 rand() 函數。

解題思路

數學問題，取兩次 rand7() 會得到一個 7 * 7 的矩形，前面 40 個可以透過 (7 * (rand7() - 1) + (rand7() - 1)) % 10 + 1 的計算取得 1 ~ 10 的數字且機率相同，若是取得後面 9 個就要重新取。

參考解法

1
2
3
4
5
6
7
8
class Solution {
public:
    int rand10() {
        int idx = 41;
        while(idx >= 40) idx = 7 * (rand7() - 1) + (rand7() - 1);
        return idx % 10 + 1;
    }
};