Topic describes

This is 470 on LeetCode. Implementing Rand10() with Rand7() is of medium difficulty.

Tag: Bit operation, math

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. Rand7 is defined.
  2. The passed argument: n represents the number of calls to RAND10.

Advanced:

  • What is the expected number of calls to RAND7 ()?
  • Can you call RAND7 () as little as possible?

Fundamental analysis

Given a function that randomly generates 111 ~ 777, it is required to implement a function that returns 111 ~ 101010 with equal probability.

First of all, it is necessary to know that quantitative global offset in the output field still satisfies equal probability, that is, to realize 000-666 random machine, only −1-1−1 operation is required on the return value of RAND7.

But the splicing/stacking of output fields does not satisfy equal probability. For example, rand7() + RAND7 () will produce numbers in the range [2,14][2, 14][2,14], but each number is not equally likely:

  • The probability of producing 222 is: 17∗17=149\frac{1}{7} * \frac{1}{7} = \ FRAc {1}{49}71∗71=491
  • The probability of producing 444 is: 17 17 17 + 17 ∗ ∗ ∗ 17 + 17 = 349 \ frac {1} {7} * \ frac {1} {7} + \ frac {1} {7} * \ frac {1} {7} + \ frac {1} {7} * \ frac {1} {7} = \ frac {3} {49} 71 71 + 71 ∗ ∗ ∗ 71 71 + 71 = 493

Among the 131313 numbers [2,14][2, 14][2,14], there are less than 101010 equal probability values.

Therefore, you should know “execute twicerand7()Together, will be
[ 1 . 10 ] [1, 10] Range of numbers to return, otherwise always retry “is an error.


k k Base you generate + reject sampling

The reason for the uneven probability distribution of the above method is that the “sum” of two different combinations of random values will produce the same result ((1,3)(1, 3)(1,3), (2,2)(2, 2), (3,1)(3, 1)(3,1) (3,1)(3, 1) and the final result is 444).

In combination, each execution of RAND7 can be considered an independent event. We can think of the results of the two RAND7 as producing the two digits of base 777. So that each value corresponds to a unique combination of random values (equal probability) and vice versa.

For example, 🌰, suppose that the results obtained by executing RAND7 randomly twice are 444 (the first time) and 777 (the second time) respectively. Since we need base 777, we can first perform the operation of −1-1−1 on the execution result of RAND7. The output field is offset to [0,6][0, 6] (still equal probability), i.e. 333 (the first time) and 666 (the second time) are obtained. Finally, the value (63)7(63)_7(63)7 is obtained, and the value (63)7(63)_7(63)7 only corresponds to our random value combination scheme. Conversely, the random value combination scheme corresponds to a unique value in base 777.

So based on what we know about base conversion, if we have arandKIs executed on
n n Times, we can produce with equal probability
[ 0 . K n – 1 ] [0, K^n – 1] Values in the range.

In this case, a single run of RAND7 can only produce less than 101010 values in the range of [0,6][0, 6]. Rand7 222 times produces values in the range of [0,48][0, 48][0,48], enough for 101010 with equal probability.

We just need to determine if the generated value is [1,10][1, 10], if it is, return it directly, otherwise keep retry.

Code:

class Solution extends SolBase {
    public int rand10(a) {
        while (true) {
            int ans = (rand7() - 1) * 7 + (rand7() - 1); // Base conversion
            if (1 <= ans && ans <= 10) returnans; }}}Copy the code
  • Time complexity: expected complexity to O (1) O (1) O (1), the worst case for O (up) (up) (\ infty) O O
  • Space complexity: O(1)O(1)O(1)

The advanced

  1. To reducerand7Number of calls to

We find that in the above solution, only the data within the range [0,48][0, 48][0,48] will be accepted and returned, and the rest will be rejected for retry.

In order to call the RAND7 method as little as possible, we can take the numbers from [0,48][0, 48][0,48] [0,48][0, 48] which are related to [1,10][1, 10] multiple numbers to perform the conversion.

We can take [0] 13 [0, 48] [0] 13 of the 40 [1] [40] 1, 40 [1] number referred to within the scope of [1, 10] [1, 10] [1, 10].

Firstly, [0,48][0, 48][1,40][1, 40] is still equal probability. Secondly, there are 444 numerical values (111, 111111, 212121, 313131) in the shape of X1x1X1. There are 444 values of the form x2x2x2 (222, 121212, 222222, 323232)… So the final result is still equal probability.

Code:

class Solution extends SolBase {
    public int rand10(a) {
        while (true) {
            int ans = (rand7() - 1) * 7 + (rand7() - 1); // Base conversion
            if (1 <= ans && ans <= 40) return ans % 10 + 1; }}}Copy the code
  • Time complexity: expected complexity to O (1) O (1) O (1), the worst case for O (up) (up) (\ infty) O O
  • Space complexity: O(1)O(1)O(1)
  1. To calculaterand7The expected number of calls

In [0,48][0, 48][0,48] we adopted values in the [1,40][1, 40][1,40] range, i.e. 4049\ FRAc {40}{49}4940 probability of being accepted in the base unit of two calls (success).

Frac {49}{49}4940 =1.225 frac{49}{40} = 1.2254049=1.225, rand7 is called twice each time, Thus, the total expected number of calls is 1.225∗2=2.451.225 * 2=2.451.225 ∗2=2.45.

The last

This is the 470th article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 questions in LeetCode by the start date, some of which have locks. We will finish all the questions without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.