Dice-Walk Winning Probability
Google● MediumNEW GRADPHONE SCREENProblem statement
Start at position 0 on an infinite one-dimensional grid. While the current position is less than mn, roll a fair k-sided die with faces 1 through k and move forward by the rolled value. Rolls are independent.
Stop immediately when the position is at least mn. Win if that stopping position is at most mx; otherwise lose. Return the exact winning probability as a floating-point value computed analytically, without Monte Carlo sampling.
Function
winningProbability(k: int, mn: int, mx: int) → doubleExamples
Example 1
k = 10mn = 1mx = 6return = 0.6The first roll ends the walk; six of the ten equally likely faces win.
Example 2
k = 2mn = 2mx = 2return = 0.75Rolling2 immediately wins with probability1/2. Rolling1 followed by1 also wins, adding1/4.
Example 3
k = 3mn = 0mx = 0return = 1.0The walk starts in its stopping interval, so no roll is made.
Constraints
1 <= k <= 10^4.0 <= mn <= mx <= 10^4.- An answer within absolute error
10^-9is accepted.