Problem Description

You are given a random number generator function rand7() that returns a uniformly distributed random integer between 1 and 7 (inclusive). Your task is to implement a function rand10() that returns a uniformly distributed random integer between 1 and 10 (inclusive).

The key constraints are:

• You can only use rand7() to generate random numbers
• You cannot use any built-in random number generation functions
• The distribution must be uniform, meaning each number from 1 to 10 should have an equal probability of being returned

The solution uses a rejection sampling technique. Here's how it works:

1. Call rand7() twice to generate two random numbers
2. The first call gives i = rand7() - 1, which produces values from 0 to 6
3. The second call gives j = rand7(), which produces values from 1 to 7
4. Combine these to create x = i * 7 + j, which generates values from 1 to 49 uniformly
5. Since we need 10 equally likely outcomes, we use only values from 1 to 40 (which is evenly divisible by 10)
6. If x > 40, reject this sample and try again
7. If x <= 40, return (x % 10) + 1 to map the 40 values uniformly to the range [1, 10]

The rejection sampling ensures that each number from 1 to 10 has exactly 4 chances out of 40 to be selected, maintaining uniform distribution. Values 41-49 are rejected to avoid bias.

Intuition

The fundamental challenge is that we need to generate 10 equally likely outcomes using a function that only produces 7 equally likely outcomes. Since 10 is not a factor of 7, we can't simply map the outputs directly.

The key insight is to create a larger uniform sample space that we can evenly divide into 10 parts. If we call rand7() twice, we can think of it as creating a 7×7 grid of possibilities, giving us 49 equally likely outcomes. We can represent each outcome uniquely by treating the two calls as digits in base 7.

By computing (rand7() - 1) * 7 + rand7(), we generate numbers from 1 to 49 uniformly. The first rand7() - 1 gives us the "row" (0-6), and multiplying by 7 shifts us to the correct row. The second rand7() gives us the "column" (1-7) within that row.

Now we have 49 uniform outcomes, but we need to map them to 10 outcomes. Since 49 is not divisible by 10, we can't use all 49 values without introducing bias. However, 40 is divisible by 10! So we use only the first 40 values and reject any result greater than 40. This rejection sampling ensures that each of the 40 accepted values has equal probability.

Finally, we map these 40 values to 1-10 using modulo arithmetic: (x % 10) + 1. This gives each number from 1 to 10 exactly 4 chances out of 40 to be selected, maintaining perfect uniformity. The rejection of values 41-49 means we might need multiple attempts, but this guarantees an unbiased result.

Solution Approach

The implementation uses rejection sampling to generate uniform random numbers from 1 to 10:

1. Generate a larger uniform distribution: We call rand7() twice to create a uniform distribution over a larger range:

   • First call: i = rand7() - 1 generates values from 0 to 6
   • Second call: j = rand7() generates values from 1 to 7
   • Combine them: x = i * 7 + j produces values from 1 to 49 uniformly

2. Rejection sampling: Since we need to map to 10 values uniformly, we only accept values from 1 to 40:

   if x <= 40:
       return x % 10 + 1

   If x > 40, we reject this sample and repeat the process by continuing the while loop.

3. Mapping to [1, 10]: For accepted values (1-40), we use modulo arithmetic to map them:

   • x % 10 gives us values from 0 to 9
   • Adding 1 shifts the range to 1 to 10
   • Each number from 1 to 10 appears exactly 4 times in the mapping (40 ÷ 10 = 4)

The while loop ensures we keep trying until we get a valid value in the range [1, 40]. Although this could theoretically loop forever, the probability of rejection is only 9/49 (about 18%), so on average, we expect to succeed quickly.

This approach guarantees that each output from 1 to 10 has exactly equal probability (1/10), maintaining the uniform distribution requirement.

Example Walkthrough

Let's walk through a few iterations to see how rand10() generates uniform random numbers:

Iteration 1:

• First call: rand7() returns 3, so i = 3 - 1 = 2
• Second call: rand7() returns 5, so j = 5
• Calculate: x = 2 * 7 + 5 = 14 + 5 = 19
• Check: Is 19 ≤ 40? Yes!
• Return: (19 % 10) + 1 = 9 + 1 = 10
• Output: 10

Iteration 2:

• First call: rand7() returns 6, so i = 6 - 1 = 5
• Second call: rand7() returns 7, so j = 7
• Calculate: x = 5 * 7 + 7 = 35 + 7 = 42
• Check: Is 42 ≤ 40? No, reject and retry
• First call: rand7() returns 1, so i = 1 - 1 = 0
• Second call: rand7() returns 8... wait, rand7() only returns 1-7, so let's say it returns 4, so j = 4
• Calculate: x = 0 * 7 + 4 = 0 + 4 = 4
• Check: Is 4 ≤ 40? Yes!
• Return: (4 % 10) + 1 = 4 + 1 = 5
• Output: 5

Iteration 3:

• First call: rand7() returns 7, so i = 7 - 1 = 6
• Second call: rand7() returns 2, so j = 2
• Calculate: x = 6 * 7 + 2 = 42 + 2 = 44
• Check: Is 44 ≤ 40? No, reject and retry
• First call: rand7() returns 4, so i = 4 - 1 = 3
• Second call: rand7() returns 3, so j = 3
• Calculate: x = 3 * 7 + 3 = 21 + 3 = 24
• Check: Is 24 ≤ 40? Yes!
• Return: (24 % 10) + 1 = 4 + 1 = 5
• Output: 5

Notice how values from 1-40 map evenly to 1-10:

• Values 1, 11, 21, 31 → output 2
• Values 2, 12, 22, 32 → output 3
• Values 10, 20, 30, 40 → output 1
• And so on...

Each output number gets exactly 4 input values mapped to it, ensuring uniform distribution.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1) expected, O(∞) worst case

The algorithm uses rejection sampling. Each iteration has a 40/49 probability of success (returning a valid result) and 9/49 probability of rejection (continuing the loop).

• Each iteration performs constant time operations: two rand7() calls and basic arithmetic
• Expected number of iterations = 1 / (40/49) = 49/40 = 1.225
• Expected number of rand7() calls = 2 * 1.225 = 2.45

Therefore, the expected time complexity is O(1). However, theoretically there's no upper bound on iterations, making worst-case O(∞).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Variables i, j, and x are the only additional storage
• No recursive calls or data structures that grow with input
• The space usage remains constant regardless of the number of iterations

Common Pitfalls

1. Incorrect Range Mapping Without Rejection

A common mistake is trying to directly map rand7() results to rand10() without proper rejection sampling:

# INCORRECT approach
def rand10_wrong():
    return (rand7() + rand7()) % 10 + 1

Why it's wrong: Simply adding two rand7() calls gives values from 2 to 14, which doesn't divide evenly by 10. This creates bias - some numbers appear more frequently than others.

Solution: Use the multiplication approach (rand7() - 1) * 7 + rand7() to create a uniform distribution from 1 to 49, then apply rejection sampling.

2. Off-by-One Errors in Index Calculation

Many implementations make mistakes with the index calculations:

# INCORRECT - doesn't generate full range
combined_value = rand7() * 7 + rand7()  # Generates 8-56, missing 1-7

Why it's wrong: Without subtracting 1 from the first rand7(), you get values starting from 8 instead of 1.

Solution: Always use (rand7() - 1) * 7 + rand7() to ensure the range starts at 1.

3. Using Wrong Rejection Threshold

Choosing an incorrect cutoff point for rejection sampling:

# INCORRECT - creates bias
if combined_value <= 49:  # Using all 49 values
    return combined_value % 10 + 1

Why it's wrong: 49 is not divisible by 10, so values 1-9 would appear 5 times while 10 appears only 4 times, creating uneven distribution.

Solution: Use 40 as the threshold since it's the largest multiple of 10 that fits within 49.

4. Forgetting the +1 in Final Mapping

A subtle but critical error:

# INCORRECT - returns 0-9 instead of 1-10
if combined_value <= 40:
    return combined_value % 10  # Missing +1

Why it's wrong: Modulo 10 gives values 0-9, but we need 1-10.

Solution: Always add 1 after the modulo operation: combined_value % 10 + 1

5. Not Using a Loop for Rejection

Attempting to handle rejection without proper retry logic:

# INCORRECT - doesn't retry on rejection
def rand10_no_loop():
    row = rand7() - 1
    col = rand7()
    combined_value = row * 7 + col
    if combined_value <= 40:
        return combined_value % 10 + 1
    else:
        return 10  # Biased fallback

Why it's wrong: Returning a fixed value or any deterministic fallback when rejection occurs introduces bias.

Solution: Use a while True loop to keep generating new random values until one falls within the acceptable range.