Leetcode 470. Implement Rand10() Using Rand7()

Problem Explanation

In this problem, we have a function rand7() that generates a random number between 1 and 7, and we are tasked with defining a new function rand10() that generates a random number between 1 and 10. For this task, we are not allowed to use a direct random function.

Let's make the problem clearer with an example. Consider we are calling rand10() for 2 times. The output will be a list and its length is 2. Each element in the list is a number between 1 and 10, which is uniformly generated.

Solution Approach

The main challenge in this problem arises from the fact that 10 is not divisible by 7, because of this, we cannot directly map the output of rand7() to rand10().

The solution lies in generating a random number between 0 and 39 using rand7() (More than 39 wouldn't cover all the 40 cases). After generating a number in the range of 0 to 39, we want to make sure that we would not exceed the range of 1 to 10, so we will take the mod 10 of the random number (providing us with a number in the range of 0 to 9) and then add 1 to shift the range to 1 to 10.

Step by step through the algorithm

1. Using rand7(), generate a base-7 random number (0-49).
2. To generate the random number, subtract 1 from rand7() result (getting us a random number between 0 and 6), multiply by 7 (getting us a number between 0 and 42 with 7 steps), then add another result of rand7(), subtracting 1 again (getting us a random number between 0 and 49).
3. If the number generated exceeds 39, repeat the previous step.
4. Once a number under 40 has been generated, simply take its remainder when divided by 10, then add 1 to get our final result.

Examples

Calling function rand10(), it uses rand7() to generate a number from 1 to 7. If we call rand10() for 3 times, the function might give us [3, 8, 4].

Python Solution

1
2python
3class Solution:
4    def rand10(self):
5        num = 40
6        while num >= 40: 
7            num = (rand7() - 1)*7 + rand7() - 1
8        return num % 10 + 1

Java Solution

1
2java
3public class Solution {
4    public int rand10() {
5        int num = 40;
6        while (num >= 40)
7            num = (rand7() - 1) * 7 + rand7() - 1;
8
9        return num % 10 + 1;
10    }
11}

JavaScript Solution

1
2javascript
3var Solution = function() {
4    
5};
6
7Solution.prototype.rand10 = function() {
8    let num = 40;
9    while (num >= 40)
10    num = (rand7() - 1) * 7 + rand7() - 1;
11    return num % 10 + 1;
12};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int rand10() {
6        int num = 40;
7        while (num >= 40)
8            num = 7 * (rand7() - 1) + rand7() - 1;
9        return num % 10 + 1;
10    }
11};

C# Solution

1
2cs
3public class Solution {
4    public int Rand10() {
5        int num = 40;
6        while (num >= 40)
7            num = (Rand7() - 1) * 7 + Rand7() - 1;
8        return num % 10 + 1;
9    }
10}

In conclusion, the problem presented can be solved by creatively using the given rand7() function to generate a number between 1 and 10 without directly using a rand10() function. The key strategy is to first obtain a random number between 0 and 49, reject any number 40 or greater, then modulate the remaining number by 10 and add 1 to result in a range from 1 to 10 inclusive that are uniformly distributed. This technique provides a general approach to the problem of generating one range of random numbers from another range, where each number in the desired range is equally likely to occur.

In each of the Python, Java, JavaScript, C++, and C# implementations, we followed a similar procedure. We created a number 40 as placeholder, then used a while loop to keep generating numbers until a number less than 40 was acquired. Inside the loop, a random number from 0-49 was computed using two calls to rand7(). Upon obtaining a number less than 40, it was then transformed into a range of 1-10 inclusive by taking the modulus by 10, and adding 1 to the result.

Understanding and applying these principles can greatly help in tackling other similar programming challenges where you have to devise a new random number generator function using an existing random number generator, or even deploying the same logic in more complex computational problems.