Expected Rolls Given the Winner of a Die Race
Updated
Problem statement
players people, numbered 0 to players - 1, take turns rolling a fair die with sides faces numbered 1 to sides. They roll in the order 0, 1, ..., players - 1, 0, 1, ..., one roll per turn.
The first roll that shows sides ends the game, and the person who rolled it wins.
Given that player winner wins, return the expected total number of rolls in the game (counting every player's rolls, including the winning one).
Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
expectedRollsGivenWin(players: int, sides: int, winner: int) → doubleExamples
Example 1
players = 2sides = 6winner = 0return = 5.545454545454546This is the interview game: two players and a normal die, and player 0 (A) rolls first. A rolls on rolls 1, 3, 5, ...
A full round of two rolls has no 6 with chance (5/6)^2 = 25/36. If A wins after j missed rounds, the game lasts 1 + 2j rolls, and that happens with chance proportional to (25/36)^j. So, given that A wins, j has mean (25/36) / (11/36) = 25/11.
The expected number of rolls is 1 + 2 × 25/11 = 61/11, about 5.5455.
Example 2
players = 2sides = 6winner = 1return = 6.545454545454546Now player 1 (B) is the winner. B rolls on rolls 2, 4, 6, ..., so the game lasts 2 + 2j rolls, with the same missed rounds j as before. The answer is 2 + 2 × 25/11 = 72/11, about 6.5455.
Example 3
players = 2sides = 2winner = 0return = 1.6666666666666667A two-faced die: each roll wins with chance 1/2. A round has no win with chance 1/4, so given that player 0 wins, the missed rounds have mean (1/4) / (3/4) = 1/3. The answer is 1 + 2 × 1/3 = 5/3.
Constraints
2 <= players <= 10002 <= sides <= 10000 <= winner < players
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
- Integers With Multiple Sum of Two CubesCharta Health · PHONE SCREEN · ONSITE INTERVIEWCharta Health interview questions
- Dice-Walk Winning ProbabilityGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Logistic Regression with Gradient DescentYahoo · PHONE SCREENYahoo interview questions
- Evaluate an Arithmetic Expression Written in WordsBrex · PHONE SCREEN
- Constant-Time Weighted Pick with an Alias TableEtched · PHONE SCREEN
- Integer to English Words in USD and INR StylesVeeam · PHONE SCREEN
- Adaptive Calibration ErrorOpenAI · PHONE SCREENOpenAI interview questions
- Sum of Smallest Non-DivisorsThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
- Square Root FunctionCitadel · PHONE SCREENCitadel interview questions
- Reorderable Task Scheduler With CooldownWaymo · PHONE SCREENWaymo interview questions