Coin With a Random Heads Chance
Updated
Problem statement
A coin has an unknown chance p of showing heads. Before any toss, p is drawn at random between 0 and 1 with density proportional to p^(a-1) × (1 - p)^(b-1). With a = b = 1 this is the uniform distribution.
The coin is then tossed n times. Once p is fixed, the tosses are independent and each shows heads with chance p.
Return the probability of getting exactly k heads.
Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
exactHeadsChance(a: int, b: int, n: int, k: int) → doubleExamples
Example 1
a = 1b = 1n = 3k = 1return = 0.25Here p is uniform. For a fixed p, one head in three tosses has chance 3p(1 - p)^2. Average it over p: 3 × ∫ p(1 - p)^2 dp = 3 × (1/2 - 2/3 + 1/4) = 3 × 1/12 = 1/4.
Example 2
a = 1b = 2n = 3k = 1return = 0.3The density of p is 2(1 - p), so the chance of tails, 1 - p, has density 2t, whose distribution function is t^2. One head in three tosses is the same as two tails in three.
The chance is ∫ 3p(1 - p)^2 × 2(1 - p) dp = 6 ∫ p(1 - p)^3 dp = 6 × 1/20 = 3/10.
Example 3
a = 2b = 2n = 4k = 2return = 0.2571428571428571The density is 6p(1 - p), so p is more likely near the middle. Two heads in four tosses has chance 6p^2(1 - p)^2 for a fixed p.
Averaging: 36 ∫ p^3(1 - p)^3 dp = 36 × 3! 3! / 7! = 36 × 36/5040 = 9/35, about 0.2571.
Constraints
1 <= a <= 10001 <= b <= 10001 <= n <= 10000 <= 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
- 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
- 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
- Count Stepping Numbers In RangeAmazon · PHONE SCREEN