Problem Description
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.
Key Insights
rand7()produces numbers from 1 to 7 with equal probability.- To generate a number from 1 to 10, we can use rejection sampling to ensure uniform distribution.
- By combining two calls to
rand7(), we can generate numbers in a larger range.
Space and Time Complexity
Time Complexity: O(1) on average, but can be O(k) in the worst case due to rejection sampling. Space Complexity: O(1), as we are using a fixed amount of space regardless of input size.
Solution
To implement rand10() using rand7(), we can utilize the output from two calls to rand7() to create a larger range of numbers. Specifically, we can create a 2D grid where the first call to rand7() determines the row and the second call determines the column. This gives us a total of 49 possible outcomes (7 rows × 7 columns). We can then map these outcomes to the desired range of 1 to 10.
However, since 49 is not a multiple of 10, we will discard any outcomes that fall outside the range of 1 to 40 (i.e., the first 4 rows of the grid). This allows us to map the remaining values uniformly to the range 1 to 10. If we get a value that falls outside this range, we simply make additional calls until we get a valid outcome.