Implement Rand 10 using Rand 7

XXX. Generate Random Number Using Rejection Sampling

Rejection Sampling

Probability

Problem Statement:

Implement a function rand10() that generates a random integer between 1 and 10 inclusive, using the given function rand7(), which generates a random integer between 1 and 7 inclusive. Optimize for uniform distribution.

Algorithm:

1. Use two calls to rand7() to generate two random integers representing a row and column in a 7x7 grid.
2. Calculate a unique index (1 to 49) from the row and column.
3. Reject indices greater than 40, as they cannot be mapped uniformly to the range 1 to 10.
4. Map the remaining indices to the range 1 to 10 using modulo arithmetic.

Complexity:

Time Complexity: O(1) (expected), as the probability of rejection converges to a constant.
Space Complexity: O(1), since no extra space is used beyond variables.

Java Implementation:

// Rejection sampling
// Use two rand7() calls to generate an index 1 to 49
// Reject all values greater than 40
// Map the remaining values to 1 to 10 using modulo
class Solution extends SolBase {
    public int rand10() {
        int row, col, idx;
        do {
            row = rand7(); // Random number for the row
            col = rand7(); // Random number for the column
            idx = col + (row - 1) * 7; // Unique index in the range [1, 49]
        } while (idx > 40); // Reject indices greater than 40
        return 1 + (idx - 1) % 10; // Map to [1, 10]
    }
}
                

Python Implementation:

def rand10():
    """
    Generate a random integer from 1 to 10 using rand7().
    """
    while True:
        row = rand7()  # Random number for the row
        col = rand7()  # Random number for the column
        idx = col + (row - 1) * 7  # Unique index in the range [1, 49]
        if idx <= 40:  # Reject indices greater than 40
            return 1 + (idx - 1) % 10  # Map to [1, 10]
                

C++ Implementation:

// Rejection sampling
// Use two rand7() calls to generate an index 1 to 49
// Reject all values greater than 40
// Map the remaining values to 1 to 10 using modulo
class Solution {
public:
    int rand10() {
        int row, col, idx;
        do {
            row = rand7(); // Random number for the row
            col = rand7(); // Random number for the column
            idx = col + (row - 1) * 7; // Unique index in the range [1, 49]
        } while (idx > 40); // Reject indices greater than 40
        return 1 + (idx - 1) % 10; // Map to [1, 10]
    }
};