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