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:
rand7is predefined.- Each testcase has one argument:
n, the number of times thatrand10is called.
Solution: Math
Time complexity: O(49/40) = O(1)
|
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua // Running time: 112 ms class Solution { public: int rand10() { int target = 40; while (target >= 40) target = 7 * (rand7() - 1) + (rand7() - 1); return target % 10 + 1; } }; |
Time complexity: O(7/6 + 7 / 5) = O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua // Running time: 112 ms class Solution { public: int rand10() { int i = INT_MAX; int j = INT_MAX; while (i > 6) i = rand7(); // i = [1, 2, 3, 4, 5, 6] while (j > 5) j = rand7(); // j = [1, 2, 3, 4, 5] return j + 5 * (i & 1); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment