Implement Rand10() Using Rand7()

Updated on 02 June, 2025
Implement Rand10() Using Rand7() header image

Problem Statement

The objective is to implement a function rand10() that generates a uniform random integer in the range [1, 10] using only an existing function rand7(). rand7() is a given API which uniformly generates a random integer between 1 and 7. The solution must rely solely on rand7() for generating randomness and is prohibited from using any built-in random functions from your programming language.

Each test case implicitly contains a parameter n, which represents how many times the rand10() function will be executed during testing. This parameter is used internally and is not explicitly passed to the rand10() function itself.

Examples

Example 1

Input:

n = 1

Output:

[2]

Example 2

Input:

n = 2

Output:

[2,8]

Example 3

Input:

n = 3

Output:

[3,8,10]

Constraints

  • 1 <= n <= 105

Approach and Intuition

  1. Recognize that rand7() gives a random integer between 1 and 7, but we need an evenly distributed way to extend this range to 1-10. Note that there are more combinations possible when using the range of 1-7 compared to 1-10.

  2. Leverage these multiple outputs from rand7() to cover a range larger than 10. One practical approach is to think in terms of a 2-dimensional matrix or a base conversion:

    • Imagine a two-dimensional (7x7) matrix filled with numbers. By calling rand7() to determine the row and another rand7() to determine the column, we can map the 49 outcomes to our desired range of 1-10.
  3. Understanding that 49 outcomes cannot be evenly distributed into 10 groups, some adjustment is needed:

    • Use a method to reduce the bias due to these excess outcomes. One strategy is to "re-roll" whenever the outcome is beyond our target range (i.e., numbers beyond 40 in a 49-grid mapping). This ensures that only results within the desired range are considered.
  4. Implement:

    • Generate first random number, num1, from rand7().
    • Generate second random number, num2, from rand7().
    • Calculate a combined index or a virtual die roll: (num1 - 1) * 7 + num2. This value now lies in [1, 49].
    • Map this result to our final range [1, 10]. If the roll result is greater than 40 (the closest multiple of 10 within 49), re-roll the two numbers.

This method should guarantee a uniform distribution as long as the re-roll probability and mapping are carefully balanced, ensuring every number from 1 to 10 in rand10() has an equal chance of 1/10.

Solutions

  • C++
  • Java
cpp
class Solution {
public:
    int generateRandom10() {
        int result, step1, step2;
        while (true) {
            step1 = rand7();
            step2 = rand7();
            result = step2 + (step1 - 1) * 7;
            if (result <= 40)
                return 1 + (result - 1) % 10;
            step1 = result - 40;
            step2 = rand7();
            // Calculate range 1-63
            result = step2 + (step1 - 1) * 7;
            if (result <= 60)
                return 1 + (result - 1) % 10;
            step1 = result - 60;
            step2 = rand7();
            // Final range 1-21
            result = step2 + (step1 - 1) * 7;
            if (result <= 20)
                return 1 + (result - 1) % 10;
        }
    }
};

The solution provided outlines an implementation of the generateRandom10() function using the predefined rand7() function. This method effectively transforms a uniform random integer generator that produces numbers from 1 to 7 (rand7) into one that produces numbers from 1 to 10 (rand10).

  • The process leverages rejection sampling, a technique where a larger number distribution is generated first and then reduced to the desired range through rejection of out-of-bounds results.
  • Start by generating a random number from 1 to 49 using two calls to rand7(). This part is achieved by:
    • Generating one number (step1) and scaling its zero-based version up by multiplying by 7, then adding another random number (step2).
    • A condition checks if the result is within the range of 1 to 40; if so, it narrows it down to the range of 1 to 10 and returns it.
  • If the initial samples are within the range 41 to 49 (and thus rejected), the method repeats the sampling process using the rejected range as the basis for another range, this time ensuring that the distribution ultimately conforms to 1 to 10:
    • It scales down repeatedly (from ranges 1-63 and 1-21, respectively), checking each result and rejecting it if it falls beyond each successive range’s maximum, ensuring that each result has an equal probability of covering the numbers 1 to 10.

This technique guarantees that the distribution of the output numbers is uniform despite starting from a smaller range and dealing with the challenge of rejection in intermediate steps. The use of such statistical methods allows for the efficient use of the random resource (rand7()) while ensuring the desired outcome range and uniform distribution.

java
class Solution extends SolBase {
    public int rand10() {
        int x, y, index;
        while (true) {
            x = rand7();
            y = rand7();
            index = y + (x - 1) * 7;
            if (index <= 40)
                return 1 + (index - 1) % 10;
            x = index - 40;
            y = rand7();
            index = y + (x - 1) * 7;
            if (index <= 60)
                return 1 + (index - 1) % 10;
            x = index - 60;
            y = rand7();
            index = y + (x - 1) * 7;
            if (index <= 20)
                return 1 + (index - 1) % 10;
        }
    }
}

The Java solution provided implements the function rand10() using the function rand7(). The primary goal is to generate a uniform distribution of integers from 1 to 10 using a function that generates numbers from 1 to 7. Here's the concise summary of how the solution works:

  • Declare integer variables x, y, and index to calculate values.
  • Enter an infinite loop to keep trying until a valid result can be returned.
  • Use combinations of repeated calls to rand7() to extend the range of random numbers beyond 7.

The code flow is structured as follows:

  1. Calculate index using two rand7() calls. The computation is adjusted to fit a 40-value grid based on the formula y + (x - 1) * 7.
  • If index lies within the first 40 numbers, scale it down modulo 10 and return the result between 1 and 10.
  1. If index falls out of the desired 40, use the remaining range to further attempt to generate a number up to 60.
  • Re-use the scaled value of index after subtracting 40, combining it with another rand7() call, and compute a new index on a smaller scale.
  • If suitable, compute and return a scaled-down modulo number.
  1. Parts of the generated range that still fall out retry with an even narrower selection based on the unused possibilities, this time up to 20.
  • Compute index again from this reduced set and, if appropriate, extract a result accordingly in the range of 1 to 10.

This method ensures all outputs of rand10() are equally probable using a rejection sampling technique, maximizing the utility of each rand7() result.

Comments

No comments yet.