LeetCode: Implement Rand10() Using Rand7()

Posted on July 17, 2018July 26, 2020 by braindenny

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:

rand7 is predefined.
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: Drop elements out of range. And map to value in the group by mod

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

Solution: Drop elements out of range. And map to which group by divide

## 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/4+1

Post Views: 3