[B] [C] [D]

The existing method RAND7 can generate uniform random integers in the range of 1 to 7. Try writing a method RAND10 to generate uniform random integers in the range of 1 to 10.

Do not use the system’s math.random () method.

Example 1:

Input: 1 Output: [7]Copy the code

Example 2:

Input: 2 output: [8,4]Copy the code

Example 3:

Input: 3 output: [8,1,10]Copy the code

Tip:

  1. rand7Have been defined.
  2. Passing in parameters:nsaidrand10The number of calls.

Advanced:

  1. rand7()call-countexpectationsHow much is?
  2. Can you make as few calls as possiblerand7() ?

Their thinking

Given rand7(), we can get uniform random integers from 1 to 7. In this case, we want to get uniform random integers from 1 to 10. To get larger numbers, we can only multiply or add them. So the first thing that comes to mind is to use rand7()*rand7() to get a uniform random integer from 1 to 49, but directly multiplying to get 1 to 49 is not uniform. So how do I get an integer greater than 7 through RAND7 ()? In fact, you can use the method of multiplying first and then adding, to achieve the following: So rand7()-1 is a uniform integer from 0 to 6, 0, 1, 2, 3, 4, 5, 6 and then you multiply them by 7 to get the following set of numbers, 0, 7, 14, 21, 28, 35, 42 uses rand7() to get random uniform integers from 1 to 7 to fill the gap, that is, add rand7() to get random uniform integers from 1 to 49. Discard the part of 40>, and get the rest %10 +1 to get uniform integers from 1 to 10.

The demo

Code implementation

var rand10 = function() { let num; Num = (rand7()-1)*7+rand7(); If (num<=40) return num%10+1}};Copy the code

Advanced implementation

Call rand7() as little as possible. In the above implementation, we dropped numbers from 41 to 49. To call RAND7 () as little as possible, we dropped numbers as little as possible. So we can use the discarded numbers and repeat the above logic to get more and more values until we end up with the fewest discarded numbers. The code is as follows:

var rand10 = function() { let num; Num = (rand7()-1)*7+rand7(); If (num<=40) return num%10+1; if(num<=40) return num%10+1; If (num<=60) return num%10+1; if(num<=60) return num%10+1; If (num<=20) return num%10+1;Copy the code

So we’re done with leetcode-470- implementing Rand10() with Rand7()

If you have any questions or suggestions, please leave a comment!