Expected Number of Runs of Heads
Updated
Problem statement
You toss a coin n times. Each toss is heads with probability p percent, independently of the other tosses.
A run of heads is a block of consecutive heads that cannot be made longer: the toss just before it and the toss just after it are tails, or do not exist. For example, HTTHHHTH has three runs of heads, of lengths 1, 3 and 1.
Return the expected number of runs of heads whose length is at least k.
Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
expectedHeadRuns(n: int, p: int, k: int) → doubleExamples
Example 1
n = 16p = 50k = 1return = 4.25This is the interview question with a fair coin. With k = 1 every run counts, and each run has exactly one first toss.
A run starts at toss 1 when toss 1 is heads: chance 1/2. A run starts at a later toss i when toss i - 1 is tails and toss i is heads: chance 1/4, for each of the 15 tosses 2 to 16. The expected count is the sum of these chances: 1/2 + 15/4 = 4.25.
Example 2
n = 8p = 30k = 1return = 1.77Heads now has chance 0.3. A run starts at toss 1 with chance 0.3, and at each of tosses 2 to 8 with chance 0.7 × 0.3 = 0.21. The answer is 0.3 + 7 × 0.21 = 1.77.
Example 3
n = 10p = 50k = 3return = 0.5625Now only runs of at least 3 heads count. Such a run starts at toss 1 when tosses 1 to 3 are heads: chance 1/8. It starts at toss i for i = 2 to 8 when toss i - 1 is tails and tosses i to i + 2 are heads: chance 1/16 each. A run of 3 cannot start at toss 9 or 10. The answer is 1/8 + 7/16 = 9/16 = 0.5625.
Constraints
1 <= k <= n <= 10^60 <= p <= 100
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
- Automation Pipeline, Part 1: Single WorkerPlaid · PHONE SCREENPlaid interview questions
- Subtract Two Large Number StringsStackAdapt · PHONE SCREENStackAdapt interview questions
- Circular Primes Below a LimitAmazon · PHONE SCREEN
- Palindrome NumberKotak Mahindra Bank · PHONE SCREENKotak Mahindra Bank interview questions
- Streaming AverageXantium · PHONE SCREEN
- Fair Coin from a Biased CoinAnthropic · PHONE SCREENAnthropic interview questions
- Stack Formula InterpreterTypeSafe AI · PHONE SCREEN
- Employee Count Median, Mean and ModeClay · PHONE SCREEN
- Newton Square Root to a Guaranteed ToleranceSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Biased Coin: Probability of Exactly h HeadsAkuna Capital · PHONE SCREENAkuna Capital interview questions