Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/470.html

470. Implement Rand10() Using Rand7() (Medium)

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:

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

Related Topics:
Random, Rejection Sampling

Solution 1.

  • /**
     * The rand7() API is already defined in the parent class SolBase.
     * public int rand7();
     * @return a random integer in the range 1 to 7
     */
    class Solution extends SolBase {
        public int rand10() {
            int num = 100;
            while (num >= 40) {
                int num1 = rand7() - 1;
                int num2 = rand7() - 1;
                num = num1 * 7 + num2;
            }
            int randNum = num / 4 + 1;
            return randNum;
        }
    }
    
  • // OJ: https://leetcode.com/problems/implement-rand10-using-rand7/
    // Time: O(1) on average, O(Infinity) in worst case
    // Space: O(1)
    class Solution {
        int rand2() {
            while (true) {
                int r = rand7();
                if (r <= 6) return 1 + (r >= 4);
            }
        }
        int rand5() {
            while (true) {
                int r = rand7();
                if (r <= 5) return r;
            }
        }
    public:
        int rand10() {
            return (rand2() - 1) * 5 + rand5();
        }
    };
    
  • # 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
            """
            return self.rand40() % 10 + 1
            
        def rand49(self):
            """
            random integer in 0 ~ 48
            """
            return 7 * (rand7() - 1) + rand7() - 1
            
        def rand40(self):
            """
            random integer in 0 ~ 40
            """
            num = self.rand49()
            while num >= 40:
                num = self.rand49()
            return num
    

All Problems

All Solutions