Strictly More Heads with Fewer Coins
Updated
Problem statement
You toss n fair coins, and the other player tosses m fair coins. Every coin lands heads or tails with chance 1/2, independently of all the others.
Return the probability that you get strictly more heads than the other player. A tie does not count as a win.
Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
moreHeadsProbability(n: int, m: int) → doubleExamples
Example 1
n = 8m = 10return = 0.2403411865234375This is the interview case: 8 coins against 10.
Your heads are more than theirs exactly when your heads plus their tails is at least 11, and that sum behaves like the number of heads in 18 fair coins. So the answer is (C(18, 11) + C(18, 12) + ... + C(18, 18)) / 2^18 = 63004 / 262144 = 15751 / 65536, about 0.24034.
Example 2
n = 11m = 10return = 0.5With one coin more than the other player, the answer is exactly 1/2. Your heads plus their tails counts heads in 21 fair coins, and you win when it is at least 11. Of 21 fair coins, at least 11 heads and at most 10 heads are equally likely, by symmetry.
Example 3
n = 1m = 1return = 0.25One coin each. You win only if your coin is heads and theirs is tails: 1/2 × 1/2 = 1/4. Both heads or both tails is a tie, which does not count.
Constraints
0 <= n, m <= 1000
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
- Biased Coin: Probability of Exactly h HeadsAkuna Capital · PHONE SCREENAkuna Capital interview questions
- Probability of Consecutive HeadsSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Count Routes Through a City GridIMC Trading · PHONE SCREENIMC Trading interview questions
- Count Clean Attendance LogsRippling · PHONE SCREENRippling interview questions
- Count Array DerangementsInMobi · PHONE SCREENInMobi interview questions
- Count Staircases with Strictly Increasing StepseBay · ONSITE INTERVIEWeBay interview questions
- Count Nondecreasing Digit-Sum ArraysMicrosoft · OAMicrosoft interview questions
- Stable Workload Redistribution TreesTower Research Capital · OA
- Count Valid A-B-C Sequences Under a Modulo-Four RuleInfosys · OAInfosys interview questions
- Count Shipment SchedulesMorgan Stanley · OAMorgan Stanley interview questions