https://leetcode.com/problems/implement-rand10-using-rand7

What we can do here is to generate numbers between 1 and 7 and this makes this problems both easy and difficult. Easy, because you do not have a lot of choice what to do, difficult, because we need to use not very big number of generations. Can we use one number between 1 and 7 to generate number between 1 and 10? I do not think so, we have very small choice. Can we use 2? Yes, we can, here is the strategy:

  1. Generate a from 1 to 7 and b from 1 to 7, then we have 7x7 = 49 options. Let us create number c = (a-1)*7 + b-1, then we can show that c is number between 0 and 48: substitute all possible values for a and b and you will see.
  2. Now, let us divide these number into groups: [0,9]; [10;19]; [20;29]; [30;39]; [40;48]. If we get into one of the first four group we are happy: there is ten number in each group, so we just return c%10 + 1.
  3. If we are in the fifth group, we are not happy, there are only 9 numbers in this group and we need 10, use 9 is not fair. So in these case, we say, that our experiment was not working, and we just start it all over again! That is all.

Complexity: what we do here is called sampling with rejection. Success of first sampling is p = 40/49. If first time our sampling was not working and it worked second time we have (1-p)*p, if it worked third time it is (1-p)*(1-p)*p and so on. Each time we use two rand7() generation. So, overall our expectation is 2*p + 4*(1-p)*p + 6*(1-p)^2*p + ... How to compute it? Note, that it is nothing else than geometrical distribution: https://en.wikipedia.org/wiki/Geometric_distribution, so the answer is just 2/p = 98/40 = 2.45.

class Solution:
    def rand10(self):
        c = (rand7() - 1)*7 + rand7() - 1
        return self.rand10() if c >= 40 else (c % 10) + 1

If you like the solution, you can upvote it on leetcode discussion section: Problem 0470