Skip to content

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.

Easy#1688
LeetCode Problem

Count of Matches in Tournament

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

Input
n = 7
Output
6
Explanation

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

Input
n = 14
Output
13
Explanation

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

1 <= n <= 200

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

  1. Observe that the tournament ends when one team remains, so exactly n - 1 teams must be eliminated.
  2. Each match produces exactly one loser and one winner, so matches and eliminations correspond one to one.
  3. A bye advances a team without eliminating anyone, so it never changes the count.
  4. 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

  1. n = 7 is odd: 3 matches are played, and 3 winners plus 1 bye leave 4 teams.
  2. n = 4: 2 matches leave 2 teams.
  3. n = 2: 1 match leaves the champion.
  4. 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.