
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
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.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 anotherrand7()
to determine the column, we can map the 49 outcomes to our desired range of 1-10.
- Imagine a two-dimensional (7x7) matrix filled with numbers. By calling
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.
Implement:
- Generate first random number,
num1
, fromrand7()
. - Generate second random number,
num2
, fromrand7()
. - 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.
- Generate first random number,
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
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.
- Generating one number (
- 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
, andindex
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:
- Calculate
index
using tworand7()
calls. The computation is adjusted to fit a 40-value grid based on the formulay + (x - 1) * 7
.
- If
index
lies within the first 40 numbers, scale it down modulo 10 and return the result between 1 and 10.
- 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 anotherrand7()
call, and compute a newindex
on a smaller scale. - If suitable, compute and return a scaled-down modulo number.
- 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.
No comments yet.