Problem Description

The task is to implement a function rand10() that generates a uniform random integer in the range 1 to 10 (inclusive), using only another function rand7() that returns a uniform random integer in the range 1 to 7 (inclusive).

• You do not have access to any other random number generators.
• rand7() is assumed to be perfectly uniform and can be called as many times as needed.
• The output of rand10() must be uniform: every integer from 1 to 10 should have an equal probability of being returned.

Thought Process

At first glance, it seems challenging to generate numbers in a range (1 to 10) using a function that only produces values in a smaller range (1 to 7). A naive approach might try to map the outputs of rand7() to 1-10, but since 7 does not divide evenly into 10, this would not be uniform.

The key insight is to use rand7() multiple times to expand the set of possible outcomes. By combining two outputs, we can simulate a larger range, such as 1 to 49 (since 7 × 7 = 49). We can then map a subset of these outcomes evenly to 1-10, discarding any results that would introduce bias.

This approach uses the idea of "rejection sampling": generate a large enough range, accept only the cases that allow an even mapping to 1-10, and retry when the result is outside that range.

Solution Approach

Let's break the algorithm down step-by-step:

1. Combine two rand7() calls:
   • Call rand7() twice to generate two random numbers, say row and col.
   • Treat these as coordinates in a 7x7 grid, so there are 49 possible outcomes.
   • Calculate a combined number: num = (row - 1) * 7 + col, which ranges from 1 to 49.
2. Map to 1-10 using rejection sampling:
   • Only use num if it falls within 1 to 40, because 40 is the largest multiple of 10 less than or equal to 49.
   • If num > 40, reject and repeat.
   • Otherwise, return 1 + (num - 1) % 10 to map uniformly to 1-10.
3. Why this works:
   • Each value from 1 to 40 is equally likely (since each grid cell is equally likely).
   • Mapping these 40 outcomes to 10 numbers gives each number exactly 4 chances, ensuring uniformity.

The process may repeat several times if the random number falls in 41-49, but on average, it is efficient.

Example Walkthrough

Suppose rand7() returns 3 and 6:

• Step 1: row = 3, col = 6
• Step 2: num = (3 - 1) * 7 + 6 = 2 * 7 + 6 = 20
• Step 3: Since 20 ≤ 40, accept it.
• Step 4: result = 1 + (20 - 1) % 10 = 1 + 19 % 10 = 1 + 9 = 10
• Result: rand10() returns 10.

If instead row = 7 and col = 1, num = 43 (which is > 40), so this attempt is discarded and the process repeats.

Time and Space Complexity

• Brute-force approach: If we tried to map 1-7 directly to 1-10, it would be impossible to guarantee uniformity, so this is not viable.
• Optimized rejection sampling approach:
  • Each call to rand10() uses two calls to rand7() per attempt.
  • The probability of accepting a number is 40/49, so the expected number of attempts is 49/40 ≈ 1.225.
  • Time Complexity: O(1) expected, since the expected number of rand7() calls is constant.
  • Space Complexity: O(1), as only a fixed number of variables are used.

Summary

The key to this problem is expanding the range of possible random values by combining outputs from rand7(), then using rejection sampling to ensure uniformity in the desired 1-10 range. By mapping the first 40 outcomes of a simulated 1-49 range to 1-10, and retrying when necessary, we achieve a simple, efficient, and elegant solution that guarantees each number is equally likely.

Code Implementation

# The rand7() API is already defined for you.
# def rand7():
#     ...

def rand10():
    while True:
        row = rand7()
        col = rand7()
        num = (row - 1) * 7 + col  # num in [1,49]
        if num <= 40:
            return 1 + (num - 1) % 10
      

// The rand7() API is already defined for you.
// int rand7();
// 
int rand10() {
    while (true) {
        int row = rand7();
        int col = rand7();
        int num = (row - 1) * 7 + col;
        if (num <= 40) {
            return 1 + (num - 1) % 10;
        }
    }
}
      

// The rand7() API is already defined for you.
// int rand7();
public int rand10() {
    while (true) {
        int row = rand7();
        int col = rand7();
        int num = (row - 1) * 7 + col;
        if (num <= 40) {
            return 1 + (num - 1) % 10;
        }
    }
}
      

/**
 * The rand7() API is already defined for you.
 * function rand7() {}
 */
var rand10 = function() {
    while (true) {
        let row = rand7();
        let col = rand7();
        let num = (row - 1) * 7 + col;
        if (num <= 40) {
            return 1 + (num - 1) % 10;
        }
    }
};