Compute the Chance of Finishing below a Score Limit
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Start at 0 points. While the score is below k, independently draw a uniformly random integer from 1 through maxPts and add it. Stop as soon as the score reaches at least k. Return the probability that the final score is at most n. The accepted error is within 0.00001 of the exact probability.
```cpp
class Solution {
public:
double new21Game(int n, int k, int maxPts);
};
```
### Examples
**Example 1:**
```text
n = 2, k = 1, maxPts = 4
Output: 0.5
Explanation: One draw stops the game, and two of the four outcomes are at most2.
```
**Example 2:**
```text
n = 2, k = 2, maxPts = 2
Output: 0.75
Explanation: A first2 wins with probability1/2; two successive1 draws add another1/4.
```
### Constraints
- Threshold and limit satisfy 0 <= k <= n <=10000.
- maxPts belongs to [1,10000].
- Answer error within 0.00001 is accepted by the source.
### Contract considerations
Preserve the independent uniform draws and stop threshold.
```hint Read the boundary condition
Which earlier scores can still contribute one more draw?
```
### Boundary reminders
Preserve the independent uniform draws and stop threshold.
Overview: Compute the Chance of Finishing below a Score Limit. Start at 0 points. While the score is below k, independently draw a uniformly random integer from 1 through maxPts and add it.