algoadvance

Given a function rand7() that generates a uniform random integer in the range of [1, 7], write a function rand10() that generates a uniform random integer in the range of [1, 10].

Clarifying Questions

  1. Is there any limitation on how many times rand7() can be called?
    • No specific limitations; however, a more efficient solution is preferred.
  2. Is rand7() guaranteed to be perfectly uniform?
    • Yes, rand7() produces each integer in the range [1, 7] with equal probability.
  3. Where should I implement rand7()?
    • For the sake of this problem, let’s assume rand7() is already implemented and available for use.

Strategy

To generate a uniform random number within [1, 10] using rand7(), we can use the following strategy:

  1. Generate a larger range of equally likely numbers using multiple calls to rand7(). Think of it as generating a two-digit number in base 7.
  2. Map this larger uniform range to a subset that fits within [1, 10]. If the result does not fit perfectly within [1, 10], reject it and try again.

Detailed Steps

  1. Use two independent calls of rand7() to generate a number in the range [1, 49] (i.e., rand7() - 1 gives us 0 to 6 which can be used simulating digits in base 7).
  2. Convert these two independent calls into one combined random number in the range [1, 49].
  3. If the generated number falls within [1, 40], map it directly to [1, 10]; otherwise, discard it and retry.

This approach ensures uniformity because each of the numbers from 1 to 49 has an equal chance, and we uniformly map a subset of this range to our desired [1, 10].

Code Implementation

import random

def rand7():
    return random.randint(1, 7)

def rand10():
    while True:
        num1 = rand7() - 1  # range 0 to 6
        num2 = rand7() - 1  # range 0 to 6
        combined = num1 * 7 + num2  # range 0 to 48
        
        # Only use the result if it's within 0 to 39
        if combined < 40:
            return (combined % 10) + 1  # range 1 to 10

# Testing rand10 function
from collections import Counter

results = [rand10() for _ in range(10000)]
counter = Counter(results)
print("Distribution of results in 10000 trials:")
for i in range(1, 11):
    print(f"{i}: {counter[i]}")

Time Complexity

The expected time complexity is O(1), though the actual time may vary since we keep retrying until we get a number within the acceptable range. The probability of needing retries is slight, so this remains efficient in practice.

  1. Each rand7() call is O(1).
  2. The expected number of retries is constant since we accept numbers in the range [1, 40] and reject from [41, 49], which implies our solution only needs a few attempts in probability terms.

Overall, the solution provides a uniform random distribution in the range [1, 10] efficiently with an expected constant time complexity.

Try our interview co-pilot at AlgoAdvance.com