Count of Matches in Tournament

Count of Matches in Tournament

What is this problem about?

You are given an integer $n$, the number of teams in a tournament. The rules are:

• If $n$ is even, $n/2$ matches are played, and $n/2$ teams advance.
• If $n$ is odd, $(n-1)/2$ matches are played, and $(n+1)/2$ teams advance. The tournament continues until only one team remains. You need to return the total number of matches played.

Why is this asked in interviews?

This is a classic "Brainteaser" asked by companies like Adobe and Meta. It tests whether a candidate can follow a simulation or if they can see a higher-level logic. While you can solve it by simulating every round, there is a very simple $O(1)$ insight that interviewers love to see.

Algorithmic pattern used

There are two patterns:

1. Simulation: Use a loop to update $n$ and add the matches round by round.
2. Mathematical Insight: In a single-elimination tournament, every match results in exactly one team being eliminated. To have 1 winner from $n$ teams, $n-1$ teams must be eliminated. Therefore, there must be exactly $n-1$ matches.

Example explanation

Let $n = 7$.

• Round 1: 7 is odd. (7-1)/2 = 3 matches. 4 teams advance.
• Round 2: 4 is even. 4/2 = 2 matches. 2 teams advance.
• Round 3: 2 is even. 2/2 = 1 match. 1 team advances.
• Total matches: $3 + 2 + 1 = 6$.
• Using the insight: $7 - 1 = 6$.

Common mistakes candidates make

The only real "mistake" is over-complicating the simulation with complex if-else logic for odd/even cases, although it usually results in the correct answer. The biggest missed opportunity is failing to notice the $n-1$ pattern, which demonstrates a strong ability to simplify problems.

Interview preparation tip

Always ask yourself: "What is being reduced or eliminated in this problem?" In tournament or game problems, counting the "losers" or "eliminations" is often much easier than counting the rounds or winners.