470. Implement Rand10() Using Rand7() - cocoder39/coco39_LC GitHub Wiki

470. Implement Rand10() Using Rand7()

rand7() generates numbers 7 numbers. To generate 10 numbers, we use result from rand7() as row index and column index to identify an item in a 7x7 table. This way we can uniformly generate 49 random numbers. Then we allocate 40 of those 49 numbers as acceptable numbers. suppose k is a number within [1, 40], then first time generate k: p = 1/49 second time generate k: p = 9/49 * 1/49 ... kth time generate k: p = (1/49)^(k-1) * 1/49

overall p = 1/49 + 9/49 * 1/49 + ... + (1/49)^(k-1) * 1/49 = 1/(1 - 9/49) * 1/49 = 1/40. As each number 1-10 repeats 4 times among those 40 numbers so the p to generate a number within [1-10] is 1/10

rand7 -> rand49 -> rand40 -> rand10

class Solution:
    def rand10(self):
        """
        :rtype: int
        """
        
        while True:
            col = rand7() - 1
            row = rand7() - 1
            index = row * 7 + col
            if index < 40:
                break
        
        return index % 10 + 1

Generalization:

Implement randM() using randN() when M < N: rand49 -> rand40 -> rand10

Implement randM() using randN() when M > N: rand7 -> rand49 -> rand40 -> rand10 (1) Implement rand11() using rand3():

public int rand11() { int result = 22; while (result >= 22) {result = 3 * 3 * (rand3() - 1) + 3 * (rand3() - 1) + (rand3() - 1);} return result % 11 + 1; } Idea: rand3() -> rand27() -> rand22 -> rand11 Time Comlexity: O(27/22)

(2) Implement rand9() using rand7():

public int rand9() { int result = 45; while (result >= 45) {result = 7 * (rand7() - 1) + (rand7() - 1);} return result % 9 + 1; } Idea: rand7() -> rand49() -> rand45() -> rand9() Time Comlexity: O(49/45)

(3) Implement rand13() using rand6():

public int rand13() { int result = 26; while (result >= 26) {result = 6 * (rand6() - 1) + (rand6() - 1);} return result % 13 + 1; } Idea: rand6() -> rand36() -> rand26 -> rand13() Time Comlexity: O(36/26)