Practice Count of Matches in Tournament
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
Start with n teams. In each round, pair teams for matches and advance one winner per match. If the number of teams is odd, one team advances without playing and all others are paired. Repeat until one team remains and return the total number of matches played.
Source: Count of Matches in Tournament on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
n = 7
6
With 7 teams, the first round has 3 matches and one team advances without playing, leaving 4 teams. The next rounds have 2 matches and then 1 final: 3 + 2 + 1 = 6. Each match eliminates exactly one team. To finish with one champion, 6 of the original 7 teams must be eliminated, which also proves the total is 7 - 1. A bye advances a team but eliminates nobody, so it must not be counted as a match.
# Example 2
n = 14
13
The rounds contain 7, 3, 2 and 1 matches. After the first round, 7 teams remain; their 3 matches and one bye leave 4 teams, followed by 2 and then 1. The total is 7 + 3 + 2 + 1 = 13. Equivalently, 14 - 1 teams must lose once. This elimination invariant works even when intermediate rounds have an odd team count; repeatedly halving without carrying the bye forward would undercount.
Constraints
How to solve Count of Matches in Tournament
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
Every match eliminates exactly one team and a bye eliminates none, so reducing n teams to a single champion always takes exactly n - 1 matches, no matter how the byes fall.
Why brute force is not enough
Simulating round by round is correct and takes only O(log n) steps, so it is not slow at n up to 200; the issue is that it misses the one-line invariant the interviewer is probing for and offers more places for integer-division mistakes on odd team counts.
Approach
- Observe that the tournament ends when one team remains, so exactly n - 1 teams must be eliminated.
- Each match produces exactly one loser and one winner, so matches and eliminations correspond one to one.
- A bye advances a team without eliminating anyone, so it never changes the count.
- Return n - 1; if asked to demonstrate by simulation, halve the field each round, adding n/2 matches for even n and (n - 1)/2 matches with (n + 1)/2 survivors for odd n, and confirm the sum matches.
Walkthrough of Example 1
n = 7 → 6
- n = 7 is odd: 3 matches are played, and 3 winners plus 1 bye leave 4 teams.
- n = 4: 2 matches leave 2 teams.
- n = 2: 1 match leaves the champion.
- 3 + 2 + 1 = 6, which equals 7 - 1 as the elimination argument predicts.
Time and space
Time O(1) · Space O(1). The closed form is a single subtraction; the simulation alternative runs O(log n) rounds, where n is the number of teams.
Interview pitfalls
- Advancing n/2 + 1 teams on an odd round with integer division, which double-counts the bye team; (n + 1)/2 is correct.
- Counting the bye as a match.
- Not handling n = 1, which should return 0 without entering any round.
- Looping while n > 0 instead of n > 1, which adds a phantom round.
Follow-up questions interviewers ask
- How many rounds does the tournament take, and why is that the ceiling of log2 n rather than the match count?
- If a match can end in a draw that sends both teams to a replay, what breaks in the invariant?
- How would you count matches in a double-elimination format where a team is out only after two losses?
Further reading on the technique: Single-elimination tournament
Related LeetCode Problems
Practice more problems similar to Count of Matches in Tournament.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.