# 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: