470

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.

// OJ: https://leetcode.com/problems/implement-rand10-using-rand7/
// Author: github.com/lzl124631x
// 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();
    }
};

Solution 2. Rejection Sampling

// OJ: https://leetcode.com/problems/implement-rand10-using-rand7/solution/
// Author: github.com/lzl124631x
// Time: O(1) on average, O(Infinity) in worst case
// Space: O(1)
// Ref: https://leetcode.com/problems/implement-rand10-using-rand7/solution/
class Solution {
public:
    int rand10() {
        while (true) {
            int r = (rand7() - 1) * 7 + rand7(); // generate evenly distributed [1, 49].
            if (r <= 40) return r % 10 + 1; // Only accept numbers in range [1, 40]
        }
    }
};