Leetcode-470. implement rand10() with rand7()

Mathematical problems

---

Topic details

Given method rand7 Generative [1,7] Uniform random integer in range , Try to write a method rand10 Generate [1,10] Uniform random integer in range .
You can only call rand7() And you can't call other methods . Please do not use the system's Math.random() Method .
Each test case will have an internal parameter n, That is, the function you implement rand10() The number of times it will be called during the test . Please note that , This is not passed on to rand10() Parameters of .

---

Example 1：

 Input : 1
 Output : [2]

Example 2:

 Input : 2
 Output : [2,8]

Example 3:

 Input : 3
 Output : [3,8,10]

Ideas :
Let's think about it first , Use rand2() Can generate [1,2] The random number , So how to get [1,4] Well ?
Do you want to use it at once rand2()+rand2() Well ?
rand2() + rand2() = ? ==> [2,4]
1 + 1 = 2
1 + 2 = 3
2 + 1 = 3
2 + 2 = 4
In order to narrow the range of generating random numbers to [1,n], So after the result of the previous step, subtract 1
(rand2()-1) + rand2() = ? ==> [1,3]
0 + 1 = 1
0 + 2 = 2
1 + 1 = 2
1 + 2 = 3
You can see , Although the result is [1,3] But the probability is not equal , So it can't be used
Then if we put (rand()2-1)×2 Well ?( How did you think of me here TM I don't know. ) We found that
(rand2()-1) × 2 + rand2() = ? ==> [1,4]
0 + 1 = 1
0 + 2 = 2
2 + 1 = 3
2 + 2 = 4
The probability is exactly equal , We have passed rand2() Realized rand4()
So we come to a mathematical law :
It is known that rand_N() Can be generated with equal probability [1, N] Random number of ranges
that ：
(rand_X() - 1) × Y + rand_Y() ==> Can be generated with equal probability [1, X * Y] Random number of ranges
It is realized. rand_XY()
Let's think about another question : How to pass in reverse rand4() Realization rand2() Well ? We can achieve by taking the remainder
rand4() % 2 + 1 = ?
1 % 2 + 1 = 2
2 % 2 + 1 = 1
3 % 2 + 1 = 2
4 % 2 + 1 = 1
in fact , as long as N yes 2 Multiple , We can all go through randN() To achieve rand2(), It's equal probability !
On the contrary, if N No 2 You cannot get equal probability by taking the remainder of the multiple of , Such as :
rand6() % 2 + 1 = ?
1 % 2 + 1 = 2
2 % 2 + 1 = 1
3 % 2 + 1 = 2
4 % 2 + 1 = 1
5 % 2 + 1 = 2
6 % 2 + 1 = 1
rand5() % 2 + 1 = ?
1 % 2 + 1 = 2
2 % 2 + 1 = 1
3 % 2 + 1 = 2
4 % 2 + 1 = 1
5 % 2 + 1 = 2
With the above regular method , We can analyze the problem , We need to get through rand7() Realization rand10()
Then we can realize randN()–N by 10 Multiple , Then take the rest
We deal with it according to the above rules :
(rand7()-1) × 7 + rand7() ==> rand49()
however 49 No 10 Multiple of ! We can use " Reject sampling "( Reject any sampling result you don't want )
hold rand49() Produced 41~49 Just refuse all and take the rest …

Code ：

// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7
class Solution 
{
    
public:
    int rand10() 
    {
    
       while (true)
       {
    
           int num = (rand7() - 1) * 7 + rand7(); //  obtain [1,49]
           if (num <= 40)   //  Reject sampling , obtain [1,40]
           return num % 10 + 1; //  Get surplus [1,10]
       } 
    }
};

Optimize

We are in the above method ," Reject sampling " 了 41-49, Then can we make rational use of these nine numbers , So as to improve the efficiency of generating random numbers , We can use 41-49 subtract 40 obtain rand9() Further get rand10(), At this time, we found that after processing again " Refuse "61-63 Three random numbers , We can use it to subtract 60 obtain rand3() Further get rand10(), At this time, the last one " Refuse " 了 21 a number , We don't need to deal with , It's over , Improves the hit rate of random numbers

// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7
class Solution 
{
    
public:
    int rand10() 
    {
    
      while (true)
      {
    
          int a = rand7();
          int b = rand7();
          int num = (a - 1) * 7 + b; // rand49()
          if (num <= 40) return num % 10 + 1; // Refuse sampling and get rand10()
        // The following code deals with the useless random numbers obtained above [41,49]
          a = num - 40; // rand49()-rand40()=rand9()
          b = rand7();
          num = (a - 1) * 7 + b; // rand63
          if (num <= 60) return num % 10 + 1; // Refuse sampling and get rand10()
        // The following code deals with the useless random numbers obtained above [61,63]
          a = num - 60; // rand3
          b = rand7();
          num = (a - 1) * 7 + b; // rand21
          if (num <= 20) return num % 10 + 1; // Refuse sampling and get rand10()
        // Further down, you can no longer make the best use of everything , Because there is only one left 21 了 

      }
    }
};