Name a Card, Win a Dollar
Updated
Problem statement
A deck has n different cards, shuffled so that every order is equally likely. The cards are turned over one at a time.
- Before the first card is turned over, you name one card.
- When the card you named is turned over, you win
$1and, if any cards are left, you name one of the cards that has not been turned over yet. - The game ends when every card has been turned over. You always know which cards have been turned over.
Return your expected winnings, the fair price to play. (Every way of choosing which card to name gives the same answer.)
Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
fairPrice(n: int) → doubleExamples
Example 1
n = 52return = 4.538043950697449This is the interview game. The answer is 1 + 1/2 + 1/3 + ... + 1/52, about 4.538, so a fair price is about $4.54. The editorial shows why.
Example 2
n = 1return = 1.0One card: you name it, it is turned over, and you win $1.
Example 3
n = 3return = 1.8333333333333333Three cards. Before each card is turned over, the card you have named is one of the cards still hidden, and each of them is equally likely to come next. So the first card is yours with chance 1/3, the second with chance 1/2, and the last with chance 1. Expected winnings: 1/3 + 1/2 + 1 = 11/6, about 1.8333.
Constraints
1 <= 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
- 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