Children, Coins and a Movie
Updated
Problem statement
n children want to go to a movie. Each child goes to a separate room and decides alone, without talking to the others, whether to come back with a fair coin. All children follow the same rule: each brings a coin with the same probability q, independently of the others.
If nobody brought a coin, they cannot go. Otherwise every coin that was brought is tossed once, and they go only if every one of those coins shows heads.
The children pick q to make going as likely as possible. Return that largest probability of going.
Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
maxMovieChance(n: int) → doubleExamples
Example 1
n = 2return = 0.3333333333333333This is the interview case. Both children bring a coin with chance q^2, and then they go with chance 1/4. Exactly one brings a coin with chance 2q(1 - q), and then they go with chance 1/2.
So the chance of going is q^2/4 + q(1 - q) = q - 3q^2/4. It is largest at q = 2/3, where it equals 2/3 - 1/3 = 1/3.
Example 2
n = 3return = 0.2991194744794363With 3 children the editorial's formula gives c = 2^(-1/2) ≈ 0.7071, the best q = (1 - c)/(1 - c/2) ≈ 0.4531, and the best chance 1 / (2 (2 - c)^2) ≈ 1 / (2 × 1.6716) ≈ 0.2991.
Example 3
n = 10return = 0.26270935258858225With 10 children, c = 2^(-1/9) ≈ 0.9259, so each child should bring a coin with chance about 0.1380. The best chance is 1 / (2 (2 - c)^9) ≈ 0.2627. More children means more chances for a tail, so each child brings a coin less often.
Constraints
2 <= n <= 10^6
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
- Integers With Multiple Sum of Two CubesCharta Health · PHONE SCREEN · ONSITE INTERVIEWCharta Health interview questions
- Dice-Walk Winning ProbabilityGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Logistic Regression with Gradient DescentYahoo · PHONE SCREENYahoo interview questions
- Evaluate an Arithmetic Expression Written in WordsBrex · PHONE SCREEN
- Constant-Time Weighted Pick with an Alias TableEtched · PHONE SCREEN
- Integer to English Words in USD and INR StylesVeeam · PHONE SCREEN
- Adaptive Calibration ErrorOpenAI · PHONE SCREENOpenAI interview questions
- Sum of Smallest Non-DivisorsThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
- Square Root FunctionCitadel · PHONE SCREENCitadel interview questions
- Reorderable Task Scheduler With CooldownWaymo · PHONE SCREENWaymo interview questions