Paying to Reroll a Die
Updated
Problem statement
You play a game with a fair die that has sides faces, numbered 1 to sides.
- Your first roll is free.
- After each roll you see the number and choose: stop and receive that many dollars, or pay
costdollars to roll again. When you roll again, the old number is lost. - You may pay to roll again at most
rerollstimes in total.
Your payoff is the number on your last roll minus all the fees you paid. Return the expected payoff when you play the best possible strategy.
Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
rerollGameValue(sides: int, cost: int, rerolls: int) → doubleExamples
Example 1
sides = 6cost = 1rerolls = 1return = 3.8333333333333335This is the interview game: a normal die and one reroll for $1.
A reroll gives a fresh roll worth 3.5 on average, minus the fee: 2.5. So reroll a 1 or a 2, and keep 3 or more. The expected payoff is (3 + 4 + 5 + 6) / 6 + 2/6 × 2.5 = 18/6 + 5/6 = 23/6, about 3.8333.
Example 2
sides = 6cost = 1rerolls = 10000return = 4.0This is the follow-up with as many $1 rerolls as you like (10^4 is more than enough). Let V be the value of the game. Rolling again is worth V - 1.
Keep 3 or more and reroll 1 and 2: V = (3 + 4 + 5 + 6) / 6 + 2/6 × (V - 1), which gives V = 4. Rolling again is worth 4 - 1 = 3, so this rule is right: a 1 or 2 is worth less than 3, and 4 or more is worth more (a 3 is a tie).
With exactly 10^4 rerolls the value is 4 - 1/2 × 3^-10000, which is 4 as a double.
Example 3
sides = 6cost = 0rerolls = 2return = 4.666666666666667Two free rerolls. With no rerolls left a roll is worth 3.5. With one left, keep 4 or more: (4 + 5 + 6) / 6 + 3/6 × 3.5 = 4.25. With two left, keep 5 or more: (5 + 6) / 6 + 4/6 × 4.25 = 14/3, about 4.6667.
Constraints
2 <= sides <= 1000 <= cost <= 1000 <= rerolls <= 10^4
More Susquehanna International Group (SIG) Phone Screen questions
- Dice Sum That Is a Multiple of mPHONE SCREEN · Seen Nov 2026
- Find Median from Data StreamPHONE SCREEN · Seen Nov 2026
- Painting Arcs to Nearest Neighbors on a CirclePHONE SCREEN · Seen Sep 2026
- Filter Movies by Inclusive Year RangePHONE SCREEN · Seen Jul 2026
- Best Single Reroll for Five DicePHONE SCREEN · Seen Feb 2026
- Catching the Bus to the MoviePHONE SCREEN · Seen Jan 2026
- Two Dice Summing to a TargetPHONE SCREEN · Seen Jan 2026
- Median of Uniform Draws in an IntervalPHONE SCREEN · Seen Oct 2025
- One Number Is the Average of the Other TwoPHONE SCREEN · Seen Jun 2025
- Which Coin Pattern Shows Up FirstPHONE SCREEN · Seen May 2025
Similar questions at other companies
- Dice-Walk Winning ProbabilityGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- 3D Grid Diagonal Walk ProbabilityApple · PHONE SCREENApple interview questions
- Coin Game From The EndsTekion · PHONE SCREENTekion interview questions
- Starting Value with the Longest Collatz ChainZipRecruiter · PHONE SCREENZipRecruiter interview questions
- Count Array DerangementsInMobi · PHONE SCREENInMobi interview questions
- Maximum-Product Subarray with an Empty ChoiceAkuna Capital · PHONE SCREENAkuna Capital interview questions
- Probability of Consecutive HeadsSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Count Staircase WaysGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- New 21 Game ProbabilityUiPath · PHONE SCREEN
- Count Stepping Numbers In RangeAmazon · PHONE SCREEN