In solving algorithm problems, we often encounter problems requiring equal probability, with Leetcode 470. For example, implement Rand10() with Rand7().

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 discuss the optimal solution, only discuss the algorithm ideas to see the problem of equal probability, we should first think of the conversion to base 2 to deal with, the idea is to let the equal probability into equal probability 0 and 1, and then from 0 and 1, increase the number to deal with the other numbers of equal probability. To disassemble the problem above we switched from Rand7 to Rand2. To return Rand2 with an equal number of zeros and ones, we can use four binary digits to generate numbers ranging from 0 to 15. Discard 10 ~ 15, keep 0 ~ 9, the result plus 1 is 1 ~ 10 random number.

The first step is to convert the binary function

The result of Rand7() is equal probability 1,2,3,4,5,6. The split is equal probability 1,2,3 and 4,5,6. Returns 0 for 1,2,3, and 1 for 4,5, and 6

declare function rand7() :number
function Rand2() :number {
	return Rand7() > 3? 1:0}Copy the code

Now we have the transition function Rand2, so let’s use random generation of 4 binary numbers and I’ll get a function that gives equal 0 to 15

function Rand15() :number {
	return Rand2() * 2 * 2 * 2 + Rand2() * 2 * 2  + Rand2() * 2  + Rand2()
}
Copy the code

The above code is a little silly, we use the shift method optimization, the left shift operator is binary carry.

function Rand15() :number {
	return (rand2() << 3) + (rand2() << 2)  + (rand2() << 1)  +  (rand2() << 0)}Copy the code

So the final Rand10() function, we just have to drop 10 ~ 15

function Rand10() :number {
	let num: number
	// Use the do while loop to return results that are less than 10, and to continue with a large roll
	do {
	  num = Rand15()
	} while ( num > 9)
  return num + 1 // Don't forget + 1
}
Copy the code

This problem solved, let’s do another problem, the idea is also binary equal probability

Given an arbitrary function f, returns 0 with probability P and 1 with probability 1-P that’s the only random mechanism you can use, how do you achieve equal probability returns 0 and 1

So again, the idea is to do it binary way, so the probability of 0 is P and the probability of 1 is 1 minus P

I can say that the probability of not zero is P times P, the probability of 11 is 1 minus P times 1 minus P, the probability of 01 is P times 1 minus P, the probability of 10 is 1 minus P times P and these two are equal.

So we just keep 01 and 10 and we get rid of 00 and 11 and we get equal probability P times 1 minus P, 10 and 01 don’t have to be equal

declare function f() : 0 | 1function round01 () : number {
	let num : number
	do {
		num = f()
  } while ( num == f())
	return num
}
Copy the code

Both quizzes are algorithmic problems solved in binary bits. There are also two general directions to solve the problem. One is to disassemble the high base numbers into equal binary equal probability, and then form the target numbers. The other is to construct equal probability by ascending.