Implement Rand10() Using Rand7() Leetcode Solution

Difficulty Level Medium
Frequently asked in ByteDance LinkedIn Microsoft Uber Yandex
Math Probability and Statistics RandomizedViews 92

Problem Statement:

Implement Rand10() Using Rand7() Leetcode Solution –  Given the API rand7() that generates a uniform random integer in the range [1, 7], write a function rand10() that produces a uniform random integer in the range [1, 10]. You can only call the API rand7(), and you shouldn’t call any other API. Please do not use a language’s built-in random API.

Each test case will have one internal argument n, the number of times your implemented function rand10() will be called while testing. Note that this is not an argument passed to rand10().

Example:

Example 1:

Input: n = 3
Output: [3, 8, 10]

Explanation:

Implement Rand10() Using Rand7() Leetcode Solution

Example 2:

Input: n = 2
Output: [2,8]

Approach:

Idea:

  1. First, we declare 2 variables, n and m, setting them initially to be rand7() and 7.
  2. Then we make sure that n is only in the 1 - 5 range and, if not, we regenerate it and assign n - 5 to m, that thus would be in the 1 - 2 range. Note that in this way n and m have the same probability of still being each specific number in their own range.
  3. In the second loop, we make sure that m has a 1 - 6 value, with similar logic of regenerating numbers until we need them.
  4. Finally, we return n or n + 5, depending if m is even or odd, respectively.

Code:

C++ Program of Implement Rand10() Using Rand7() :

class Solution {
public:
    int rand10() {
        int n, m;
        n = rand7(), m = 7;
        
    while (n > 5) {
            m = n - 5;
            n = rand7();
        }
       
    while (m == 7) m = rand7();
        return (m % 2 ? 5 : 0) + n;
    }
};

Java Program of Implement Rand10() Using Rand7() :

class Solution extends SolBase {
    public int rand10() {
        int n, m;
        n = rand7();
        m = 7;
        
    while (n > 5) {
            m = n - 5;
            n = rand7();
        }
       
    while (m == 7) m = rand7();
        if (m % 2 == 0) return n;
        else return n+5;
    }
}

Complexity Analysis for Implement Rand10() Using Rand7() Leetcode Solution:

Time Complexity:

The Time Complexity of the code is  O(1) in the average case but in the worst case.

Space Complexity:

The Space Complexity of the code is O(1) because we don’t need any extra space to solve this problem.

Question to practice randomized problems:

Insert Delete GetRandom O(1) Leetcode Solution

Translate »