Leetcode: Implement Rand10() Using Rand7()

Implement Rand10() Using Rand7()



Similar Problems:


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.

Do NOT use system’s Math.random().

Example 1:

Input: 1
Output: [7]

Example 2:

Input: 2
Output: [8,4]

Example 3:

Input: 3
Output: [8,1,10]

Note:

  1. rand7 is predefined.
  2. Each testcase has one argument: n, the number of times that rand10 is called.

Follow up:

  • What is the expected value for the number of calls to rand7() function?
  • Could you minimize the number of calls to rand7()?

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
## Blog link: https://code.dennyzhang.com/implement-rand10-using-rand7
## Basic Ideas:
##  f(7) -> f(49) -> f(40) -> f(10)
##    0 - 48: 6*x+y
##    0 - 39
##       0, 10, 20, 30 -> 0
##       1, 11, 21, 31 -> 1
##       2, 12, 22, 32 -> 2
##       ...
##    0 - 9
##    1 - 10
## Complexity:
# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7
class Solution:
    def rand10(self):
        """
        :rtype: int
        """
        res = 40
        while res>=40:
            res = 7*(rand7()-1) + (rand7()-1)
        return res%10+1
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.