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 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.randintor similar; we must rely solely on calls torand7(). - 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
- Generating Entropy: A single call to
rand7()gives us bits of entropy. To get uniform distribution over[1, 10], we need enough combinations fromrand7calls that cover the target space evenly without bias. - Mapping Ranges: If we call
rand7()twice, we can generate a number in range using base-7 arithmetic:(r1 - 1) * 7 + r2. This creates a uniform distribution over[1, 49]. - 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 values where is a multiple of 10 that fits in our range. The largest such number is 40.- If we get a value between
1and40, we map it to[1, 10]. Specifically:(val - 1) % 10 + 1. This covers exactly four full cycles of the target range (since ). - If we get a value between
41and49, it is “wasted” entropy. We must reject this outcome, retry generating two new numbers fromrand7(). This ensures uniformity at the cost of occasional retries.
- If we get a value between
Approach
We use Rejection Sampling.
- Call
rand7()twice to generate a number in[1, 49]using(r1 - 1) * 7 + r2. - Check if this generated value is .
- If yes: Map it to the target range and return immediately. The mapping formula
((val - 1) % 10) + 1ensures uniformity across[1, 10]. - If no (value > 40): Discard this result and repeat step 1.
- This loop guarantees a valid output eventually with probability approaching 1.
Complexity Analysis
- Time: Expected . The rejection sampling follows a geometric distribution. Probability of success per iteration is . Expected number of iterations is , so expected
rand7calls per call torand10()is roughly times the target range size logic, but strictly speaking per call torand10, we expect calls torand7. - Space: 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 , this is a probabilistic event with probability approaching zero over time; practically impossible to hit in finite execution windows for standard test cases (). - Uniformity: The modulo mapping
((num - 1) % 10) + 1applied strictly on the subset[1, 40]guarantees that each number 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 providedrand7()API calls.