[python] O(n) rand10() using **2 calls** to rand7()

The following is a simple, readable solution in python to Aug 28th's Question of the Day:

Best case: 2n calls to rand(7)
Average (Expected) case: (7/6 + 7/5)n = 2.57n calls to rand(7)
Worst case: "infinite" calls to rand(7) since you could theoretically get a string of 7s on multiple calls to rand7.

In layman's terms:

  1. Pick a random number between 1-6.
  2. Pick a random number between 1-5.
  3. If the first number is 1, 3, or 5, return the second number. If it's 2, 4, or 6, return the second number plus five.

Explanation:
your first number decides if you return a number between 1-5 or 6-10. Since it's 50-50 chance to get odd vs even in your first number, you have a 50-50 chance of returning 1-5 or 6-10. Then since you chose your second number randomly (using rand7), you have a 1/5 chance of returning (5+)1,2,3,4,5. 1/5 * 1/2 = 1/10 prob for each number 1-10.

        # create "finalNum" between 1 and 5
        # if oddOrEven is even, return "finalNum" plus 5 (a num between 6-10)
        # if oddOrEven is odd, return finalNum (a num between 1-5)
        
        # get random number between 1-6
        oddOrEven = rand7()
        while oddOrEven == 7:
            oddOrEven = rand7()
            
        # get random number between 1-5
        finalNum = rand7()
        while finalNum >= 6:
            finalNum = rand7()

        # if first num is even, return second num +5. else return first num
        if oddOrEven%2==0:
            return finalNum+5
        return finalNum```
Comments (1)