Domain 2MediumCORE

Implement Rand10() Using Rand7()

We are given a black-box API rand7() that returns an integer uniformly distributed in [1, 7]. We need to implement rand10() which must return integers uniformly distributed in [1, 10].

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Random#Rejection Sampling

470. Implement Rand10() Using Rand7()

Model: qwen3.5:9b
Topics: Random,Rejection Sampling
FAANG asked: 1
Acceptance rate: 46.1%


Problem Breakdown

We are given a black-box API rand7() that returns an integer uniformly distributed in [1, 7]. We need to implement rand10() which must return integers uniformly distributed in [1, 10].

Key Constraints:

  • Uniformity is critical: Every number from 1 to 10 must have exactly a 1/101/10 probability of being returned. Naive modulo operations (e.g., (rand7() + rand7()) % 10) introduce bias because the source range size isn’t divisible by the target range size.
  • No Built-in Random: We cannot use random.randint or similar; we must rely solely on calls to rand7().
  • Efficiency: While correctness is primary, minimizing expected API calls (rand7) is a follow-up requirement and good practice for production systems (cost of randomness).

Intuition

  1. Generating Entropy: A single call to rand7() gives us log⁡2(7)\log_2(7) bits of entropy. To get uniform distribution over [1, 10], we need enough combinations from rand7 calls that cover the target space evenly without bias.
  2. Mapping Ranges: If we call rand7() twice, we can generate a number in range [1,49][1, 49] using base-7 arithmetic: (r1 - 1) * 7 + r2. This creates a uniform distribution over [1, 49].
  3. Rejection Sampling: Since 49 is not divisible by 10, we cannot map all 49 outcomes to rand10() without bias (some numbers would appear more often). We can safely use the first kk values where kk is a multiple of 10 that fits in our range. The largest such number ≤49\le 49 is 40.
    • If we get a value between 1 and 40, we map it to [1, 10]. Specifically: (val - 1) % 10 + 1. This covers exactly four full cycles of the target range (since 40/10=440 / 10 = 4).
    • If we get a value between 41 and 49, it is “wasted” entropy. We must reject this outcome, retry generating two new numbers from rand7(). This ensures uniformity at the cost of occasional retries.

Approach

We use Rejection Sampling.

  1. Call rand7() twice to generate a number in [1, 49] using (r1 - 1) * 7 + r2.
  2. Check if this generated value is ≤40\le 40.
  3. If yes: Map it to the target range and return immediately. The mapping formula ((val - 1) % 10) + 1 ensures uniformity across [1, 10].
  4. If no (value > 40): Discard this result and repeat step 1.
  5. This loop guarantees a valid output eventually with probability approaching 1.

Complexity Analysis

  • Time: Expected O(1)O(1). The rejection sampling follows a geometric distribution. Probability of success per iteration is p=40/49≈0.82p = 40/49 \approx 0.82. Expected number of iterations is 1/p1/p, so expected rand7 calls per call to rand10() is roughly 2/(40/49)=2.452 / (40/49) = 2.45 times the target range size logic, but strictly speaking per call to rand10, we expect ≈2.45\approx 2.45 calls to rand7.
  • Space: O(1)O(1) auxiliary space for variables and loop state.

Solution

def rand10():
    while True:
        # Generate a number in range [1, 49] using two calls to rand7()
        r1 = rand7() 
        r2 = rand7()
        
        # Map the pair (r1, r2) into base-7 representation for uniform distribution over [1, 49]
        num = (r1 - 1) * 7 + r2
        
        # If we fall within our valid range of multiples of 10 (<= 40), map to [1, 10]
        if num <= 40:
            return ((num - 1) % 10) + 1

Edge Cases Handled

  • Infinite Loop Risk: Theoretically, if rand10() keeps generating values > 40 indefinitely, the loop never terminates. However, since P(success)=40/49P(\text{success}) = 40/49, this is a probabilistic event with probability approaching zero over time; practically impossible to hit in finite execution windows for standard test cases (n≤105n \le 10^5).
  • Uniformity: The modulo mapping ((num - 1) % 10) + 1 applied strictly on the subset [1, 40] guarantees that each number x∈[1,10]x \in [1, 10] appears exactly 4 times in every valid batch of 40 outcomes.
  • API Constraints: We do not use any built-in random libraries (like random) or external entropy sources; we strictly rely on the provided rand7() API calls.