Implement Rand10() Using Rand7() - Practice Coding Problems

Implement Rand10() Using Rand7() - Problem

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

You can only call the API rand7(), and you shouldn't call any other API. Please do not use a language's built-in random API.

Each test case will have one internal argument n, the number of times that your implemented function rand10() will be called while testing. Note that this is not an argument passed to rand10().

Input & Output

Example 1 — Basic Execution

$ Input: Call rand10() once

› Output: 7

💡 Note: rand7() returns 3 and 4, giving (3-1)*7+4=18. Since 18 ≤ 40, return (18-1)%10+1 = 8. Note: actual output is random, this shows the process.

Example 2 — Rejection Case

$ Input: Call rand10() once

› Output: 2

💡 Note: First: rand7() returns 6,7 giving 42 > 40, reject. Second: rand7() returns 1,3 giving 3, return (3-1)%10+1 = 3. Shows rejection sampling in action.

Example 3 — Distribution Check

$ Input: Call rand10() 1000 times

› Output: Each number 1-10 appears roughly 100 times

💡 Note: Over many calls, each output from 1 to 10 should appear with equal probability (~10%), demonstrating uniform distribution.

Constraints

You must only use the given rand7() API
Do not use any other random number generator
The output must be uniformly distributed over [1, 10]
Each call to rand10() should be independent

Visualization

Tap to expand

Understanding the Visualization

Input

rand7() API generating uniform integers 1-7

Transform

Use rejection sampling to create uniform 1-10 distribution

Output

rand10() function returning uniform integers 1-10

Key Takeaway

🎯 Key Insight: Use rejection sampling to transform distributions while preserving uniformity

Asked in

f Facebook 15 G Google 12 🍎 Apple 8

The key insight is to use rejection sampling to maintain uniform distribution. Generate a larger uniform range using multiple rand7() calls, then map to the target range while rejecting values that would break uniformity. The optimal approach uses multi-phase rejection sampling to minimize expected calls. Time: O(1) expected, Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Analysis Approach	O(1)	O(1)	Understand the theoretical foundation and entropy requirements
Optimized Rejection Sampling	O(1)	O(1)	Reuse rejected values to minimize expected calls to rand7()
Basic Rejection Sampling	O(1)	O(1)	Generate numbers 1-40 using two rand7() calls, reject values > 40

Mathematical Analysis Approach — Algorithm Steps

Calculate entropy requirements
Design optimal mapping strategy
Minimize expected number of calls
Implement with theoretical backing

Visualization

Tap to expand

Step-by-Step Walkthrough

Entropy Calculation

rand7(): 2.807 bits, rand10(): 3.322 bits

Minimum Calls

3.322 ÷ 2.807 = 1.183 calls theoretical minimum

Efficiency Analysis

Each phase maximizes acceptance probability

Practical Implementation

Multi-phase approach approaching optimum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

int rand7() {
    return rand() % 7 + 1;
}

int solution() {
    // Theoretical minimum calls: log2(10)/log2(7) ≈ 1.183
    // This implementation approaches the theoretical limit
    
    while (1) {
        // Phase 1: Generate 1-40 from 1-49 (efficiency 40/49 ≈ 81.6%)
        int num = (rand7() - 1) * 7 + rand7();
        if (num <= 40) {
            return (num - 1) % 10 + 1;
        }
        
        // Phase 2: Use remainder 1-9, expand to 1-63 (efficiency 60/63 ≈ 95.2%)
        num = (num - 41) * 7 + rand7();  // 0-8 * 7 + 1-7 = 1-63
        if (num <= 60) {
            return (num - 1) % 10 + 1;
        }
        
        // Phase 3: Use remainder 1-3, expand to 1-21 (efficiency 20/21 ≈ 95.2%)
        num = (num - 61) * 7 + rand7();  // 0-2 * 7 + 1-7 = 1-21  
        if (num <= 20) {
            return (num - 1) % 10 + 1;
        }
        
        // Continue recursively with single remainder
        // In practice, we rarely get here
    }
}

int main() {
    srand(time(NULL));
    printf("%d\n", solution());
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Expected constant time approaching theoretical minimum

✓ Linear Growth

Space Complexity

O(1)

Only uses constant additional variables

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Analysis Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler