# 470. 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.

# Solution

Approach 1: rejection sampling.

# Code (Python)

Approach 1:

    def rand10(self):  
        # rejection sampling: build a mapping from (rand1, rand2) to 1~10
        #   1 2 3 4 5 6 7 --> rand2
        #----------------
        #1| 1 2 3 4 5 6 7
        #2| 8 9 x 1 2 3 4
        #3| 5 6 ...
        #4|
        #5|
        #6|
        #7|
        while True:
            rand1, rand2 = rand7(), rand7()
            index = rand1 + (rand2 - 1) * 7 # rand2 as rows, rand1 as columns
            if index <= 40:
                return (index - 1) % 10 + 1 # this index is 1 based, so need -1 to make it 0 based

        # Expectation: geometric distribution with passing probability P(pass) = 40/49
        # With 2 calls per iteration, E(# of calls): 49/40 * 2 = 2.45
        
        # Improvement: when index falls in range 41 - 49, we essentially got a rand9().
        # Make a rand7() again and do rejection sampling for 60 out of 7*9=63. Can repeat this ...

# Code (C++)

Approach 1:

Approach 2: