Code Implementation

class Solution:
    def numberOfMatches(self, n: int) -> int:
        matches = 0
        while n > 1:
            matches += n // 2
            n = (n + 1) // 2
        return matches
      

class Solution {
public:
    int numberOfMatches(int n) {
        int matches = 0;
        while (n > 1) {
            matches += n / 2;
            n = (n + 1) / 2;
        }
        return matches;
    }
};
      

class Solution {
    public int numberOfMatches(int n) {
        int matches = 0;
        while (n > 1) {
            matches += n / 2;
            n = (n + 1) / 2;
        }
        return matches;
    }
}
      

var numberOfMatches = function(n) {
    let matches = 0;
    while (n > 1) {
        matches += Math.floor(n / 2);
        n = Math.floor((n + 1) / 2);
    }
    return matches;
};
      

Problem Description

You are given an integer n representing the number of teams in a single-elimination tournament. In each round, teams are paired up for matches; the winner of each match advances to the next round, and the loser is eliminated. If the number of teams is odd, one team advances automatically to the next round without a match (a "bye"). The process repeats until only one team remains, who becomes the winner.

Your task is to determine the total number of matches played throughout the tournament, given n teams.

• Each match eliminates one team.
• There is only one winner at the end.
• Input: an integer n (number of teams, n >= 1).
• Output: the total number of matches played.

Thought Process

Let's start by understanding the tournament structure. In each round, teams are paired up and play matches. The winners move on. If the number of teams is even, everyone is paired. If it's odd, one team gets a bye and automatically advances.

A brute-force approach would be to simulate each round: pair teams, count matches, and repeat until one remains. But let's think: in every match, one team is eliminated. Since there is only one winner, the number of eliminated teams is n - 1. So, the total number of matches should also be n - 1, because each match eliminates exactly one team.

However, let's also consider the simulation approach, which is more in line with how the problem might be coded: in each round, count the number of matches as n // 2 (integer division), update n to the number of teams advancing (winners + any team with a bye), and repeat.

Solution Approach

There are two main ways to solve this problem:

• Simulation Approach:
  1. Initialize a variable matches to 0.
  2. While there are more than one team:
     • Calculate the number of matches in this round: n // 2.
     • Add this to matches.
     • Update n to the number of teams advancing: (n + 1) // 2 (winners plus a possible bye).
  3. Return matches.
• Direct Formula:
  • Since each match eliminates one team and only one team remains, the answer is always n - 1.
  • This is a mathematical shortcut, but the simulation approach is often preferred for clarity and to match the problem's description.

In our implementation, we use the simulation approach for clarity and to demonstrate the elimination process step by step.

Example Walkthrough

Let's consider n = 7 teams:

1. First round:
   • Teams: 7
   • Matches: 7 // 2 = 3
   • Teams advancing: 3 winners + 1 bye = 4
   • Total matches so far: 3
2. Second round:
   • Teams: 4
   • Matches: 4 // 2 = 2
   • Teams advancing: 2 winners = 2
   • Total matches so far: 3 + 2 = 5
3. Third round:
   • Teams: 2
   • Matches: 2 // 2 = 1
   • Teams advancing: 1 winner = 1
   • Total matches so far: 5 + 1 = 6
4. End:
   • Only one team remains.
   • Total matches played: 6

Time and Space Complexity

• Brute-force (Simulation) Approach:
  • Each iteration halves the number of teams, so the number of rounds is O(log n).
  • Each round does constant work, so total time is O(log n).
  • Space complexity is O(1) since only a few variables are used.
• Optimized (Direct Formula) Approach:
  • Time complexity: O(1) since it’s a single subtraction.
  • Space complexity: O(1).

Summary

The problem asks for the total number of matches in a single-elimination tournament. The key insight is that every match eliminates one team, so with n teams, there must be n - 1 matches. The simulation approach mirrors the actual tournament process and is easy to implement, while the direct formula is a mathematical shortcut. Both are efficient, but the simulation provides more clarity for beginners and matches the problem's narrative.