Implement Rand10() Using Rand7()

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.

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.