Implement Rand10 Using Rand7 - Leetcode Solution

Problem Statement: Given a function rand7 which generates a uniformly random integer in the range 1 to 7, write a function rand10 which generates a uniformly random integer in the range 1 to 10.

Approach: We cannot simply generate a random number in the range 1 to 10 using rand7 as they are not evenly distributed. We have to use some randomization and maybe generate more numbers than needed and reject if they do not fall in the given range.

To solve this problem, we can implement the following algorithm:

• Generate two random numbers i, j using rand7().
• Calculate n = (i-1)*7 + j-1, which uniformly generates values in the range 0 to 48.
• If n >= 40, reject it and return to step 1.
• Otherwise, return n % 10 + 1 which generates a uniform number in the range 1 to 10.

Let's understand why this algorithm works:

• Because i and j are both uniformly random, n is also uniformly random in the range 0 to 48.
• By rejecting values of n >= 40, we ensure that the remaining values of n (0 to 39) are uniformly random in the range 0 to 39.
• Finally, by taking the modulus (%) with 10 and adding 1, we get a uniform distribution in the range 1 to 10.

Code:

class Solution {
public:
    int rand10() {
        int i, j, n;
        do {
            i = rand7();
            j = rand7();
            n = (i-1)*7 + j-1;
        } while (n >= 40);
        return n % 10 + 1;
    }
};

Time Complexity: The expected time complexity of the algorithm is O(1) as the probability of rejecting is less than 25%. Space Complexity: The space complexity is constant O(1) as we are not using extra space for our calculations.

This solution satisfies the given problem statement and passed all the test cases on Leetcode.

1