470. Implement Rand10() Using Rand7()
Problem Description
The problem provides a rand7() API, which produces a uniformly distributed random integer in the range from 1 to 7. The objective is to create a new function rand10() that generates a random integer in the range from 1 to 10 with a uniform distribution, utilizing only the rand7() function. It is important to achieve this without using any other random functions provided by the programming language's built-in libraries. Additionally, the function rand10() will be called n times during testing, where n is an internal argument used for testing purposes. It is crucial that the distribution of the numbers generated by rand10() is uniform, meaning each number from 1 to 10 has an equal probability of occurrence, leveraging the randomness provided by rand7().
Intuition
To solve this problem, the idea is to find a way to generate a range that is a multiple of 10 using rand7(), because this would allow us to easily map the results to a 1-10 range uniformly. Since rand7() produces numbers from 1 to 7, we can simulate a larger range by treating one call to rand7() as the digit in one place of a base-7 number, and another call as the digit in another place.
Here's the reasoning:
- Call
rand7()to get a numberibetween 0 and 6 (inclusive) by subtracting 1 from the result. - Call
rand7()again to get a numberjbetween 1 and 7 (inclusive). - Combine
iandjto generate a numberx= i * 7 + j. The numberxis now uniformly distributed between 1 and 49 becauseihas 7 possible outcomes andjalso has 7 possible outcomes, which means we have 7 * 7 = 49 possibilities.
But, we need a range that is a multiple of 10 to map to the range 1 to 10. So what we do is:
- We only use the results 1 through 40 from
x. This ensures that whenxis within this range, each number has an equal probability of occurring because 40 is a multiple of 10. - If
xis greater than 40, we discard it and try again. This way we make sure every result from 1 to 10 will have an equal likelihood. - The result needs to be in the range 1 to 10, so we take
x % 10which gives us a range from 0 to 9, then add 1 to shift this range to 1 to 10.
The process of discarding numbers and trying again is called rejection sampling, which ensures we can get a uniform distribution in the desired range.
Learn more about Math patterns.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Solution Approach
The solution approach for implementing the rand10() function using the rand7() API involves the concept of rejection sampling, which is a technique where you generate a sample and only use it if it falls within a certain range. The aim is to produce a uniform distribution between 1 and 10 by generating a larger uniform distribution and narrowing it down.
Here is a step-by-step breakdown of the algorithm used in the given implementation:
-
Start an infinite loop to keep trying until a valid sample is produced. This loop will terminate once we get a number in the desired range.
-
Generate two independent numbers
iandjby callingrand7(). We usei = rand7() - 1to get a number from 0 to 6, andjis just the output fromrand7(), which ranges from 1 to 7.This step effectively simulates rolling two 7-sided dice, one to determine the tens' place (with possible results 0 to 6 corresponding to 00, 07, 14, ..., 42) and one to determine the ones' place (with possible results 1 to 7). You could imagine it as creating a two-digit base-7 number (
ibeing the first digit andjthe second digit). -
Compute
x = i * 7 + j, which gives us a uniform distribution in the range of 1 to 49 because there are 7 possible states theican take on, and for each state ofi, there are 7 possible states ofj. Therefore, the total possible outcomes are 7 * 7 = 49. -
Use rejection sampling to discard values of
xgreater than 40. This rejection is necessary because we want to be able to evenly distribute outcomes in the range of 1 to 10, and we cannot do that with 49 outcomes since 49 is not divisible by 10. The closest number less than 49 that is divisible by 10 is 40, so we limitxto this range. -
If
xis less than or equal to 40, we take the modulo ofxwith 10, which gives a result ranging from 0 to 9. By adding 1 to this result, we shift the range to 1 to 10, the desired outcome forrand10(). -
Return the final result which is now guaranteed to be uniformly distributed between 1 and 10.
No additional data structures are needed for this solution; only variables to store the two numbers generated by rand7() and to calculate x.
In summary, the algorithm ensures a uniform distribution for the rand10() function by creating a larger uniform distribution using rand7(), and narrowing it down using rejection sampling and modulo operation to fit within the required range.
Depth first search can be used to find whether two components in a graph are connected.
Example Walkthrough
Let's walk through a small example to illustrate the solution approach.
Suppose we want to generate a random number from 1 to 10 using the rand7() function. We'll show one potential sequence of events:
-
We start our process and enter an infinite loop where we will keep generating numbers until we get a result less than or equal to 40. Let's say we call
rand7()and it returns 5. According to our algorithm, we need to subtract 1 to convert this to a 0-based range, so we now havei = 4. -
We call
rand7()again for our second number and it returns 3. We do not modify this number, soj = 3. -
Next, we compute
xusing the formulax = i * 7 + j. Substituting in our values, we getx = 4 * 7 + 3 = 31. Since the result, 31, falls in the range of 1 to 40, we can use it. -
We use rejection sampling to check if the value of
x(31) is less than or equal to 40. In this case, it is true, so there is no need to discard this value and retry. -
The next step is to translate our
xrange of 1 to 40 to 1 to 10, so we takex % 10. For our example, this is31 % 10, which equals 1. -
The final result of 1 is not in the range of 1 to 10, so we add 1 to shift the range:
1 + 1equals 2. -
We have our final result for this iteration: 2. This number is a valid output of our
rand10()function and is uniformly distributed across the range from 1 to 10. Ifrand10()were to be called multiple times, each number from 1 to 10 would have approximately a 1 in 10 chance of being produced, satisfying the conditions of the problem.
Solution Implementation
1class Solution:
2 def rand10(self):
3 """
4 Generate a random integer in the range 1 to 10 using the provided rand7() function.
5
6 :rtype: int
7 """
8 while True:
9 # Generate two independent numbers from 1 to 7.
10 # Subtract 1 from the first number to make it range from 0 to 6.
11 row = rand7() - 1
12 col = rand7()
13
14 # Calculate a unique number in the range 1 to 49 (7x7 grid)
15 value = row * 7 + col
16
17 # If the number is within the first 40 numbers, use it for a uniform distribution from 1 to 10.
18 if value <= 40:
19 # The modulo operation ensures a uniform distribution [0, 9].
20 # Adding 1 adjusts the range to [1, 10].
21 return value % 10 + 1
221class Solution extends SolBase {
2 public int rand10() {
3 // Continue the loop until a suitable number is generated
4 // which can be scaled down to the range 1 to 10
5 while (true) {
6 // Generate a number from 0 to 6 using rand7()
7 int row = rand7() - 1;
8 // Generate another number from 1 to 7 using rand7()
9 int col = rand7();
10 // Calculate index in a 7x7 matrix
11 int idx = row * 7 + col;
12 // Check if the index is within the range we can use
13 // Which is the first 40 numbers of the 7x7 matrix.
14 // This is important to maintain the uniform distribution of rand10.
15 if (idx <= 40) {
16 // Use modulus to scale the result to be within 1 to 10 and return
17 return idx % 10 + 1;
18 }
19 // If index is greater than 40, reject it and try again
20 }
21 }
22}
231// The rand7() API is already defined for the user.
2// int rand7();
3// @return a random integer in the range 1 to 7
4
5class Solution {
6public:
7 int rand10() {
8 while (true) {
9 // Generate two random numbers using rand7
10 int row = rand7() - 1; // Subtracting 1 to get a range from 0 to 6.
11 int col = rand7(); // Keeping range as 1 to 7.
12
13 // Calculate a new index from the two random numbers to get a range from 1 to 49.
14 int index = row * 7 + col;
15
16 // Check if the index is within the range we can use to generate a random number from 1 to 10.
17 if (index <= 40) {
18 // Use the modulo operation to get a final result in the range from 1 to 10.
19 return index % 10 + 1;
20 }
21 // If the index is greater than 40, discard the number and try again.
22 // This is done to avoid a skewed distribution that could occur due to the reject sampling.
23 }
24 }
25};
261/**
2 * Utilizes the predefined rand7() function to generate a random number between 1 and 10.
3 * @return {number} A random integer in the range 1 to 10
4 */
5function rand10(): number {
6 while (true) {
7 // Generate two independent numbers from the rand7() to increase the range
8 const num1 = rand7() - 1; // Subtract 1 to make it from 0 to 6, enabling multiplication
9 const num2 = rand7();
10
11 // Combine the two numbers to get a number in the range of 1 to 49
12 const combinedNum = num1 * 7 + num2;
13
14 // Check if the generated number can be evenly distributed within 1-10
15 if (combinedNum <= 40) {
16 // If within the desired range, use modulo operation to get a number from 1 to 10
17 return (combinedNum % 10) + 1;
18 }
19
20 // If the number is greater than 40, repeat the process
21 // This ensures that each number from 1 to 10 has an equal probability of being returned
22 }
23}
24Which data structure is used to implement recursion?
Time and Space Complexity
The given Python code uses a rejection sampling method to generate a uniform distribution from 1 to 10 using the rand7() function.
Time Complexity:
The time complexity of rand10() is not constant, as it depends on the number of times the while loop executes before generating a number less than or equal to 40. Since we generate a number between 1 and 49 (7 * 7 possibilities), and only the numbers from 1 to 40 are used, the probability p of stopping at each iteration is 40/49. Thus, the expected number of iterations E is 1/p, which is 49/40. Due to the constant work in each iteration, the expected time complexity is O(1/p) = O(49/40), which simplifies to O(1) since we disregard constants in Big O notation.
However, please note that this is the expected time complexity. The worst-case time complexity is unbounded because in theory, it's possible (though extremely unlikely) that the while loop could run indefinitely if the condition x <= 40 is never met.
Space Complexity:
The space complexity of the rand10() method is O(1) as it uses only a constant amount of additional space. Variables i, j, and x are used, but their space usage does not scale with the size of the input, so the space complexity is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.