Sponsored
Sponsored
The rejection sampling method involves generating a larger range of values than needed using multiple calls to rand7(), then rejecting any values that fall outside the desired range. The goal is to convert an output range span (like 1 to 7) to another (like 1 to 10). You can do this by mapping combinations of rand7() outputs together.
The idea is to create a smaller uniform distribution using a larger one and then scale it down to the desired range.
The expected time complexity is O(1), but the actual time depends on the success rate of generating a number that falls within the desired range. The space complexity is O(1) since we only use a limited amount of storage regardless of input size.
1def rand10():
2 while True:
3 row = rand7()
4 col = rand7()
5 result = (row - 1) * 7 + col
6 if result <= 40:
7 return 1 + (result - 1) % 10In the Python implementation, the sequence of rand7() calls expands the probability space to 49 possible outcomes. It rejects any number greater than 40, limiting the effect of bias when scaling to a 1-10 outcome range.
This approach explores random walks over a 2D grid formed by two calls to rand7(). By defining a grid dimension and using rerolls for values that fall outside of a specific boundary, it effectively resamples portions of the distribution space.
We consider a grid of 7x7 points and use this combined space to extract valid outcomes for our 1-10 range.
The average time complexity is O(1) due to expected constant writes, but can vary based on rerolls. The space used is fixed so the space complexity is O(1).
int rand10() {
int num;
do {
num = 7 * (rand7() - 1) + rand7();
} while (num > 40);
return num % 10 + 1;
}The C++ implementation likewise operates on the grid layout, resampling positions until they're in a suitable subset. It maps these consistently to the desired outcome range between 1 and 10.