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.

// 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();
    }
};

Solution 2. Rejection Sampling

// OJ: https://leetcode.com/problems/implement-rand10-using-rand7/solution/

// 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]
        }
    }
};

Java

/**
 * 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;
    }
}

All Problems

All Solutions