Fewest Games to Find the Top Two Teams
Updated
Problem statement
There are n teams, and no two of them are equally strong. You do not know the strengths. In a game between two teams, the stronger team always wins.
You choose games one at a time, and each choice may depend on the results so far. You want to know which team is the best and which team is the second best.
Return the smallest number g such that some way of choosing games always finds both teams within g games, whatever the strengths are.
Function
fewestGamesForTopTwo(n: int) → intExamples
Example 1
n = 100return = 105This is the interview question. Run a knockout: every game removes one team, so the best team is found after 99 games. With byes, the field shrinks 100, 50, 25, 13, 7, 4, 2, 1, so the champion plays at most 7 games.
The second-best team lost only to the champion, so it is one of the at most 7 teams the champion beat. A knockout among them takes at most 6 more games. That is 99 + 6 = 105 games, and the editorial shows that no method can always do it in fewer.
Example 2
n = 3return = 3Say A beats B in the first game. The second game must bring in C. If it is A against C and A wins, we still do not know whether B or C is second. If it is B against C and C wins, we still do not know whether A or C is best. Either way some results need a third game, and 3 games are always enough.
Example 3
n = 8return = 9A knockout of 8 teams takes 7 games and has 3 rounds, so the champion beat exactly 3 teams. A knockout among those 3 takes 2 more games, for 7 + 2 = 9.
Constraints
2 <= n <= 10^9
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
- IP Address to CIDR BlocksOpenAI · PHONE SCREENOpenAI interview questions
- Raise a Number to an Integer PowerAdobe · PHONE SCREENAdobe interview questions
- Count the 1 Bits in a 32-Bit ValueAmazon · PHONE SCREEN
- Choose the Next Minesweeper ActionRunloop · PHONE SCREEN
- Power of Two Without DivisionArm · PHONE SCREEN
- Powers of Two in a RangeAkuna Capital · PHONE SCREENAkuna Capital interview questions
- Count Subarrays with a Perfect-Square ProductMicrosoft · OAMicrosoft interview questions
- Repeated Mirror XORMathWorks · OAMathWorks interview questions
- Minimum Power-of-Two Removal OperationsIBM · OAIBM interview questions
- Minimum Power-of-Two Removal OperationsVisa · OAVisa interview questions