#837
New 21 Game
specialist · 905 · lc medium +31 · verified · 52% accepted · 2,492 likes · top 42%
Description
Alice plays a card game loosely inspired by "21".
She starts with 0 points and keeps drawing as long as her score is below k. Each draw adds a uniformly random integer from [1, maxPts] to her score. Draws are independent.
She stops as soon as her score reaches k or higher.
Return the probability that Alice finishes with at most n points.
Answers within 10-5 of the true value are accepted.
Example 1:
Input: n = 10, k = 1, maxPts = 10
Output: 1.00000
Explanation: Alice gets a single card, then stops.
Example 2:
Input: n = 6, k = 1, maxPts = 10
Output: 0.60000
Explanation: Alice gets a single card, then stops.
In 6 out of 10 possibilities, she is at or below 6 points.
Example 3:
Input: n = 21, k = 17, maxPts = 10
Output: 0.73278
Code
1
2
3