Implement Rand10() Using Rand7()

1. Start an infinite loop.
2. Generate a number idx from 1 to 49 using the formula: idx = (rand7() - 1) * 7 + rand7(). This requires two calls to rand7().
3. Check if idx is within the usable range [1, 40].
4. If idx <= 40, the number is accepted. Calculate the result as (idx - 1) % 10 + 1 and return it.
5. If idx > 40, the number is rejected. The loop continues, and we try again from step 2.

The core idea is to generate a number in a range larger than 10 and then map it down. A single call to rand7() gives 7 outcomes, which is not enough to map to 10 uniform outcomes. Two calls to rand7() give 7 * 7 = 49 equally likely outcomes. We can map these 49 outcomes to numbers from 1 to 49. A common way is to use a base-7 mapping: (rand7() - 1) * 7 + rand7(). This generates a uniform random integer in the range [1, 49]. To get a uniform rand10(), we need a range that is a multiple of 10. We can use the numbers from 1 to 40 from our generated range [1, 49]. If the generated number is between 1 and 40 (inclusive), we can map it to a number between 1 and 10. The formula (number - 1) % 10 + 1 achieves this uniformly. If the generated number is greater than 40 (i.e., 41 to 49), we "reject" this result and repeat the entire process by calling rand7() twice again. This is necessary to maintain uniformity, as we cannot map the 9 leftover numbers (41-49) to 10 outcomes fairly. This process is repeated until a valid number (1-40) is generated.

1/**2 * The rand7() API is already defined in the parent class SolBase.3 * public int rand7();4 * @return a random integer in the range 1 to 75 */6class Solution extends SolBase {7    public int rand10() {8        while (true) {9            int row = rand7();10            int col = rand7();11            int idx = (row - 1) * 7 + col; // Generates a uniform number in [1, 49]12            if (idx <= 40) {13                return (idx - 1) % 10 + 1;14            }15        }16    }17}

1. Start an infinite loop.
2. First Level: Generate num1 = (rand7() - 1) * 7 + rand7(). This gives a uniform number in [1, 49].
3. If num1 <= 40, return (num1 - 1) % 10 + 1.
4. Second Level: We have a rejected number from [41, 49]. This is a rand9(). Let val9 = num1 - 40.
5. Generate num2 = (val9 - 1) * 7 + rand7(). This gives a uniform number in [1, 63].
6. If num2 <= 60, return (num2 - 1) % 10 + 1.
7. Third Level: We have a rejected number from [61, 63]. This is a rand3(). Let val3 = num2 - 60.
8. Generate num3 = (val3 - 1) * 7 + rand7(). This gives a uniform number in [1, 21].
9. If num3 <= 20, return (num3 - 1) % 10 + 1.
10. Restart: The number was 21. This is a rand1(). We have no more randomness to extract, so we continue the loop from the beginning.

This method starts the same way as the basic approach: generate a number idx from 1 to 49. If idx is in [1, 40], we accept it and return (idx - 1) % 10 + 1. The key difference is what happens when idx > 40. Instead of discarding the result and starting over, we recognize that we have just generated a uniform random number in the range [41, 49]. This is equivalent to generating a uniform random number from 1 to 9 (by subtracting 40). Let's call this rand9(). Now, the problem is to generate rand10() given a rand9() and the rand7() function. We can combine our rand9() result with a new call to rand7() to generate an even larger range. Using the formula (rand9() - 1) * 7 + rand7(), we can generate a uniform random number in the range [1, 63]. This only required one additional rand7() call. From this new range [1, 63], we can use the numbers [1, 60]. If our number falls in this range, we return (number - 1) % 10 + 1. If the number is in [61, 63], we have generated a rand3(). We can repeat the process again: combine this rand3() with a new rand7() call to get a rand21(). From [1, 21], we can use [1, 20]. If the number is in this range, we return the result. If the number is 21, we have a rand1(), which provides no new randomness. At this point, we have exhausted the utility of the rejected values and must restart the entire process from the beginning. This cascading use of rejected ranges significantly reduces the probability of needing to start over completely, thus lowering the expected number of rand7() calls.

1/**2 * The rand7() API is already defined in the parent class SolBase.3 * public int rand7();4 * @return a random integer in the range 1 to 75 */6class Solution extends SolBase {7    public int rand10() {8        while (true) {9            // First attempt: generate rand49, use [1, 40]10            int num49 = (rand7() - 1) * 7 + rand7();11            if (num49 <= 40) {12                return (num49 - 1) % 10 + 1;13            }14            15            // Reuse the rejected range [41, 49] -> [1, 9]16            int num9 = num49 - 40;17            // Second attempt: combine rand9 with rand7 to get rand63, use [1, 60]18            int num63 = (num9 - 1) * 7 + rand7();19            if (num63 <= 60) {20                return (num63 - 1) % 10 + 1;21            }22 23            // Reuse the rejected range [61, 63] -> [1, 3]24            int num3 = num63 - 60;25            // Third attempt: combine rand3 with rand7 to get rand21, use [1, 20]26            int num21 = (num3 - 1) * 7 + rand7();27            if (num21 <= 20) {28                return (num21 - 1) % 10 + 1;29            }30            31            // Rejected [21], must restart32        }33    }34}