algoadvance

Leetcode 470. Implement Rand10() Using Rand7()

Problem Statement

The task is to implement a function int rand10() that utilizes a given API function int rand7(), which generates a uniform random integer in the range [1, 7], to generate a uniform random integer in the range [1, 10].

Clarifying Questions

  1. Does rand7() generate truly random integers uniformly?
    • Yes, each integer from 1 to 7 is equally likely to be generated.
  2. Are there any constraints in terms of performance or the number of calls to rand7()?
    • It is generally desirable to minimize the number of calls to rand7() to improve performance. The solution should balance simplicity and efficiency.
  3. Is there a limit on how many times rand7() can be called?
    • Typically, no hard limit is given, but making fewer calls is usually better in terms of performance.

Strategy

To use rand7() to generate a uniform distribution from 1 to 10, one straightforward way is to consider generating numbers in the range [1, 49] using two calls of rand7(), as 7 * (rand7() - 1) + rand7() covers ranges from 1 to 49 uniformly:

  1. Utilize two calls to rand7() to create a range from 1 to 49:
    • Let a = rand7() - 1 be an integer in [0, 6].
    • Let b = rand7() be an integer in [1, 7].
    • Then, calculate val = a * 7 + b, which produces an integer in [1, 49].

  2. If the generated integer val is in the range [1, 40], use val % 10 + 1 to get a number in the range [1, 10].

  3. If val is outside the range [1, 40], reject it and repeat the process (rejection sampling).

This method ensures that each number between 1 and 10 has an equal probability of being selected.

Code

#include <cstdlib>

// Given API
int rand7();

int rand10() {
    int val;
    do {
        // Generate a uniform number in the range [1, 49]
        int a = rand7() - 1;
        int b = rand7();
        val = a * 7 + b; // (a * 7) gives values in multiples of 7, then add b.
    } while (val > 40); // Since we only need numbers in the range [1, 40]

    return (val - 1) % 10 + 1; // Normalize [1, 40] to [1, 10]
}

Time Complexity

The expected time complexity for this solution is O(1), although the actual number of iterations in the loop depends on the probability of generating values in the range [1, 40] from [1, 49]. Specifically, the loop runs an average of 1.225 times per call to rand10(), since the probability of acceptance is 40/49.

Therefore, this solution is efficient both in terms of implementation complexity and performance.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI