Rand1 generates rand9

1. Problem description

This is a piece of me in 20220706 Wednesday morning at Shenzhen Science Park D1 Algorithm problems encountered in participating in futu social recruitment .

Given a function rand1 Meeting 50% The probability output of 0 and 1, Please use rand1 Realization rand9, Output with equal probability 0~9 this 10 A digital .

2. Difficulty level

The difficulty should be middle.

3. Solutions

From the point of view of the subject , There is a known condition ,rand1() Meeting 50% The probability output of 0 and 1, Implement a new function on the basis of known conditions rand9(), So it's equivalent to based on 50% The probability generator creates a 10% Probability generator .

How to create a 10% What about the event generator , We know from the formula ,rand1 Probability of occurrence P(0)=50%,P(1)=50%, that rand1 Perform twice , That is, both results are 1 The probability of is 25%, Three times it turned out to be 1 The probability of is 12.5%, All four executions are 1 The probability of is 6.25%, Equivalent to four times 1111 The probability of combination is 6.25%, That is to say 1/16.

Is this data familiar ？ We use the program to generate it four times 0 and 1 The number of combinations produced ：

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

It's a binary number , After converting to decimal , Namely 0~15, amount to 16 The probability of occurrence of each number is 1/16; in other words , produce 0 To 9 The probability is equal , Although the probability is not 1/10.

So the solution of this problem is to reject the sampling method ： call 4 Time rand1, Generate 4 The binary number of bits , And then convert it to 10 Hexadecimal number , If this number is greater than 9, Then regenerate .

4. Implementation example

Use Golang Give an implementation example .

First of all, we realize rand1.

package main

import (
	"math/rand"
)

// rand1  Equal probability output  0  and  1.
func rand1() int {
    
	return rand.Intn(2)
}

According to rand1 Realization rand9：

// rand9  Equal probability output  0 ~ 9.
func rand9() int {
    
	for {
    
		n := rand1()<<3 + rand1()<<2 + rand1()<<1 + rand1()
		if n < 10 {
    
			return n
		}
	}
}

rand9 Output example ：

1
4
8
6
9
3
2
2
8
5

---

reference

It is known that f(x) Incoming value Equal probability Output 0 or 1, If you write one f1(x） Achieve equal probability output 0-9？| segmentfault
use Rand7() Realization Rand10() | LeetCode