Chance of at Least k Heads
Updated
Problem statement
You toss n fair coins. Each lands heads with probability 1/2, independently of the others.
Return the probability that you get at least k heads.
Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
atLeastHeads(n: int, k: int) → doubleExamples
Example 1
n = 100k = 61return = 0.017600100108852407More than 60 heads in 100 tosses means at least 61. The exact answer is (C(100, 61) + C(100, 62) + ... + C(100, 100)) / 2^100, about 0.0176.
The normal approximation (mean 50, standard deviation 5, cut at 60.5) gives about 0.0179: close, but not within 10^-9.
Example 2
n = 400k = 220return = 0.025520111564573993At least 220 heads from 400 coins. The exact answer is about 0.02552. With mean 200 and standard deviation 10, the normal approximation cut at 219.5 gives about 0.02559.
Example 3
n = 4k = 2return = 0.6875Four coins: 2, 3 or 4 heads happen in 6 + 4 + 1 = 11 of the 16 equally likely outcomes, so the answer is 11/16 = 0.6875.
Constraints
1 <= n <= 10^60 <= k <= n
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
- Count Array DerangementsInMobi · PHONE SCREENInMobi interview questions
- Biased Coin: Probability of Exactly h HeadsAkuna Capital · PHONE SCREENAkuna Capital interview questions
- Revolver: Will the Next Shot Fire?Tower Research Capital · PHONE SCREEN
- Probability of Consecutive HeadsSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Expected Fake-Name CollisionsMercor · PHONE SCREENMercor interview questions
- Election District Budget Allocation AnalysisIMC Trading · PHONE SCREENIMC Trading interview questions
- Count Clean Attendance LogsRippling · PHONE SCREENRippling interview questions
- Extra Coin Win ProbabilityMicrosoft · PHONE SCREENMicrosoft interview questions
- Count Staircases with Strictly Increasing StepseBay · ONSITE INTERVIEWeBay interview questions
- Get Triplet CountIBM · OAIBM interview questions