470. Implement Rand10() Using Rand7() #

Problem #

Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.

Do NOT use system’s Math.random().

Example 1:

Input: 1
Output: [7]

Example 2:

Input: 2
Output: [8,4]

Example 3:

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

Note:

1. rand7 is predefined.
2. Each testcase has one argument: n, the number of times that rand10 is called.

Follow up:

1. What is the  expected value for the number of calls to rand7() function?
2. Could you minimize the number of calls to rand7()?

Problem Summary #

There is an existing method rand7 that can generate a uniform random integer in the range 1 to 7. Try to write a method rand10 to generate a uniform random integer in the range 1 to 10. Do not use the system’s Math.random() method.

Notes:

• rand7 is predefined.
• Input parameter: n represents the number of times rand10 is called.

Follow-up:

• What is the expected value of the number of calls to rand7()?
• Can you call rand7() as few times as possible?

Solution Ideas #

• Given rand7(), implement rand10().
• rand7() generates 1, 2, 3, 4, 5, 6, 7 with equal probability. To obtain rand10(), i.e., generate 1-10 with equal probability. The idea is to first construct a randN(), where N must be an integer multiple of 10, and then randN % 10 can give rand10(). So we can first construct rand49() from rand7(), then filter out all values in rand49() that are greater than or equal to 40, thereby obtaining rand40(), and then take modulo 10.
• Specific construction steps, rand7() --> rand49() --> rand40() --> rand10():
  1. rand7() generates 1,2,3,4,5,6,7 with equal probability.
  2. rand7() - 1 generates [0,6] with equal probability.
  3. (rand7() - 1) *7 generates 0, 7, 14, 21, 28, 35, 42 with equal probability
  4. (rand7() - 1) * 7 + (rand7() - 1) generates these 49 numbers [0, 48] with equal probability
  5. If the result of step 4 is greater than or equal to 40, then repeat step 4 until the generated number is less than 40
  6. Take the result of step 5 mod 10 and then add 1, which will randomly generate [1, 10] with equal probability
• This problem can be generalized to the problem of generating a random number of any range. Use randN() to implement randM(), where M>N. The steps are as follows:
  1. First use randN() to implement randX(), where X ≥ M, and X is an integer multiple of M. For example, 49 > 10 in this problem;
  2. Then use randX() to generate randM(), as in this problem: 49 —> 40 —> 10.
• For example, to use rand3() to generate rand11(), you can first generate rand27(), then set the threshold to 22, because 22 is a multiple of 11. The way to generate rand27() is: 3 * 3 * (rand3() - 1) + 3 * (rand3() - 1) + (rand3() - 1), and finally rand11() is generated; to use rand7() to generate rand9(), you can first generate rand49(), then set the threshold to 45, because 45 is a multiple of 9. The way to generate rand49() is: (rand7() - 1) * 7 + (rand7() - 1), and finally rand9() is generated; to use rand6() to generate rand13(), you can first generate rand36(), then set the threshold to 26, because 26 is a multiple of 13. The way to generate rand36() is: (rand6() - 1) * 6 + (rand6() - 1), and finally rand13() is generated;

Code #

package leetcode

import "math/rand"

func rand10() int {
	rand10 := 10
	for rand10 >= 10 {
		rand10 = (rand7() - 1) + rand7()
	}
	return rand10%10 + 1
}

func rand7() int {
	return rand.Intn(7)
}

func rand101() int {
	rand40 := 40
	for rand40 >= 40 {
		rand40 = (rand7()-1)*7 + rand7() - 1
	}
	return rand40%10 + 1
}