We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Implement Rand10() Using Rand7()

Number: 903

Difficulty: Medium

Paid? No

Companies: Google, LinkedIn, Microsoft

Problem Description

Given an API rand7() that returns a uniform random integer in the range [1, 7], implement a function rand10() that returns a uniform random integer in the range [1, 10] using only calls to rand7().

Key Insights

  • The problem can be solved using rejection sampling.
  • By combining two calls to rand7(), we can generate a uniform integer in the range [1, 49].
  • If the generated number is between 1 and 40, it can be mapped to the range [1, 10] uniformly.
  • If the number falls in the range [41, 49], it is discarded and the process is repeated.
  • This method guarantees uniform distribution for rand10().

Space and Time Complexity

Time Complexity: Expected O(1) per call (with a constant expected number of iterations due to rejection sampling)
Space Complexity: O(1)

Solution

The solution involves using rejection sampling:

  1. Generate a number in the range [1, 49] by combining two rand7() calls: calculate num = (rand7() - 1) * 7 + rand7().
  2. If num is less than or equal to 40, use (num - 1) % 10 + 1 to convert it into a number in the range [1, 10].
  3. If num is greater than 40, reject the number and repeat the process. This approach uses rejection sampling to ensure that each number in the range [1, 10] is equally likely.

Code Solutions

import random

# Assume rand7() is defined as below.
def rand7():
    return random.randint(1, 7)

# Function to generate a uniform random integer from 1 to 10 using rand7()
def rand10():
    while True:
        # Generate a number in [1, 49]
        num = (rand7() - 1) * 7 + rand7()
        # Accept if the number is in [1, 40]
        if num <= 40:
            return (num - 1) % 10 + 1

# Example usage:
print(rand10())
← Back to All Questions