Count of Matches in Tournament - Solution & Explanation

Problem Overview: You are given n teams in a knockout tournament. Each round pairs teams to play matches, and the winner advances to the next round. If the number of teams is odd, one team automatically advances. The goal is to count the total number of matches played until a single champion remains.

Approach 1: Iterative Reduction Approach (Simulation) (Time: O(log n), Space: O(1))

This method directly simulates how the tournament progresses. In each round, compute how many matches are played based on the number of teams. If n is even, n / 2 matches occur and n / 2 teams advance. If n is odd, (n - 1) / 2 matches occur and one team automatically advances, leaving (n - 1) / 2 + 1 teams for the next round. Repeat this process using a loop until only one team remains, accumulating the total number of matches along the way. This is a straightforward simulation approach that mirrors the real tournament structure and is useful when practicing iterative reasoning problems.

Approach 2: Direct Mathematical Calculation (Time: O(1), Space: O(1))

The key insight comes from observing what happens in every match: exactly one team is eliminated. Starting with n teams and ending with one champion means n - 1 teams must be eliminated. Since each match eliminates exactly one team, the total number of matches played must be n - 1. This eliminates the need for simulation entirely. The result can be returned immediately with a simple formula. This solution relies on basic math reasoning rather than step‑by‑step iteration, making it the most efficient and elegant approach.

Recommended for interviews: Start with the simulation approach to show you understand how the tournament rounds work. Then present the mathematical insight that each match removes one team, leading to the formula n - 1. Interviewers typically expect the constant-time math solution because it demonstrates problem simplification and analytical thinking.