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.
1#include <stdio.h>
2int rand7();
3int rand10() {
4 int result;
5 do {
6 int row = rand7();
7 int col = rand7();
8 result = (row - 1) * 7 + col;
9 } while (result > 40);
10 return 1 + (result - 1) % 10;
11}
In this C solution, we first generate two random numbers (row and column) using rand7()
. We then map these to a single number in the range [1,49]. We repeatedly generate numbers until we get a result in the range [1,40] to ensure uniformity. The final transformation scales this number to [1,10].
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).
1 public int Rand10() {
int num;
do {
num = 7 * (Rand7() - 1) + Rand7();
} while (num > 40);
return num % 10 + 1;
}
}
C# follows the same boundary-exploring pathway using a 2D space of choice, rejecting any infeasible outcome, extending retries until landing on a 1-10 compatible number.