Expected Flips for k Heads in a Row
Updated
Problem statement
You flip a fair coin again and again. Each flip is heads or tails with equal chance, independently of the others. You stop as soon as the last k flips were all heads.
Return the expected number of flips you make. The answer is always a whole number.
Function
expectedFlips(k: int) → longExamples
Example 1
k = 3return = 14Let E0, E1 and E2 be the expected number of flips still needed when the current run of heads has length 0, 1 and 2. Each flip either extends the run or, on tails, sends you back to a run of 0: E2 = 1 + E0/2, E1 = 1 + E2/2 + E0/2 and E0 = 1 + E1/2 + E0/2. Solving gives E0 = 14.
Example 2
k = 1return = 2Each flip is heads with chance 1/2, so the first head comes after 2 flips on average.
Example 3
k = 2return = 6You first need a head, which takes 2 flips on average. One more flip then ends the game half the time; on tails you start again from nothing. So E = 2 + 1 + E/2, which gives E = 6.
Constraints
1 <= k <= 50
More Jane Street Phone Screen questions
- Maximum-Scoring Consecutive Tree LevelsPHONE SCREEN · Seen Nov 2026
- Tree Selection and VisibilityPHONE SCREEN · Seen Nov 2026
- Load/Store Arithmetic InterpreterPHONE SCREEN · Seen Oct 2026
- Instrument Stack Language JumpsPHONE SCREEN · Seen Oct 2026
- Run a Stack Language InterpreterPHONE SCREEN · Seen Oct 2026
- Positive-Integer Expression EvaluationPHONE SCREEN · Seen Oct 2026
- Add Two Integers Given as StringsPHONE SCREEN · Seen Sep 2026
- Angle Between Clock HandsPHONE SCREEN · Seen Jul 2026
- Route Length From Two CyclistsPHONE SCREEN · Seen Jul 2026
- Sort TradesPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
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
- Median of Uniform Draws in an IntervalSusquehanna International Group (SIG) · PHONE SCREENSusquehanna International Group (SIG) 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