Given the API rand7() that generates a uniform random integer in the range [1, 7], write a function rand10() that generates a uniform random integer in the range [1, 10]. You can only call the API rand7(), and you shouldn't call any other API. Please do not use a language's built-in random API.
Each test case will have one internal argument n, the number of times that your implemented function rand10() will be called while testing. Note that this is not an argument passed to rand10().
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
Follow up:
rand7() function?rand7()?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.
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].
C++
Java
Python
C#
JavaScript
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.
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.
This C solution simulates a random walk over a 2D 7x7 grid. By leveraging grid positions, it discards values outside the boundary, essentially repeating the attempt until a valid number is extracted which can then map consistently to range 1-10.
C++
Java
Python
C#
JavaScript
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).
| Approach | Complexity |
|---|---|
| Rejection Sampling Method | 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. |
| Random Walk on a 2D Grid | 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). |
Implement Rand10() Using Rand7() | LeetCode 470 | C++, Java, Python • Knowledge Center • 6,219 views views
Watch 9 more video solutions →Practice Implement Rand10() Using Rand7() with our built-in code editor and test cases.
Practice on FleetCode