470. Implement Rand10() Using Rand7()

• 470. Implement Rand10() Using Rand7()
  • Description
  • Intuition
    • Naive Solution
    • Advanced Solution
    • Generalization
  • Pitfall
  • Solution
  • Reference

Description

Intuition

Naive Solution

Very intuitively, you can generate rand7() 10 times and get an generator uniformly distributed [0, 70)

  public int rand10() {
    int sum = 0;
    for (int i = 0; i < 7; i++) {
      sum += rand7();
    }
    return sum % 10 + 1;
  }

Advanced Solution

public int rand10() {
    int result = 40;
    while (result >= 40) {result = 7 * (rand7() - 1) + (rand7() - 1);}
    return result % 10 + 1;
}

in the solution above, it will generate [0, 40) uniformly, and then, normalize the result;

Proof:

P(result = k) </p> = P(rand49() = k in the 1st iteration) + </p> P(rand49() > 40 in the 1st iteration) P(rand49() = k in the 2nd iteration) + </p> P(rand49() > 40 in the 1st iteration) P(rand49() > 40 in the 2nd iteration) P(rand49() = k in the 3rd iteration) + </p> P(rand49() > 40 in the 1st iteration) P(rand49() > 40 in the 2nd iteration) P(rand49() > 40 in the 3rd iteration) P(rand49() = k in the 4th iteration) + </p> ... </p> = (1/49) + (9/49) (1/49) + (9/49)^2 (1/49) + (9/49)^3 (1/49) + ... </p> = (1/49) [1 + (9/49) + (9/49)^2 + (9/49)^3 + ... ] </p> = (1/49) [1/(1-9/49)] </p> = (1/49) (49/40) </p> = 1/40 </p>

Generalization

Implement randM() using randN() when M > N: Step 1: Use randN() to generate randX(), where X >= M. 可以用 randN() + N * randN() + N * N * randN() + ... + N^(n + 1) * randN() 来产生 Step 2: Use randX() to generate randM().

Pitfall

Solution

Naive Solution

Advanced Solution

Reference

Three-line Java solution, the idea can be generalized to "Implement RandM() Using RandN()"-Using-RandN()%22)