470. Implement Rand10() Using Rand7() (Medium)

https://leetcode.com/problems/implement-rand10-using-rand7/

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()?

Solutions

class Solution extends SolBase {
    public int rand10() {
        int row;
        int col;
        int idx;

        do {
            row = rand7();
            col = rand7();

            // The probability of getting 1,2,...49 are same, be aware that 50 is not present.
            // And the random data set is not integer multiple of 10, which result in the unrandom
            // sequence after executing below statement.

            // The workaround is to keep a set of which the size is integer multiple of 10,
            // say [1~10], [1~20], [1~30], [1~40], [20~30], [20~40], [30~40], the best option is [1~40]
            // since it carries the largest probability that 40/49 chance the data will locate in this
            // range and the loop times will be minimized.

            idx = col + (row - 1) * 7;
        } while (idx > 40);

        return 1 + (idx - 1) % 10;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""