Problem Description

You have n teams competing in a tournament with special pairing rules:

• When the number of teams is even: Each team pairs with exactly one other team. This results in n / 2 matches being played, and n / 2 teams move forward to the next round.

• When the number of teams is odd: One team gets a bye (advances automatically without playing), while the remaining teams pair up. This results in (n - 1) / 2 matches being played, and (n - 1) / 2 + 1 teams advance to the next round.

The tournament continues round by round until only one winner remains. Your task is to calculate the total number of matches played throughout the entire tournament.

The elegant solution recognizes that in any tournament format where each match eliminates exactly one team, you need exactly n - 1 matches to determine a winner from n teams. This is because you start with n teams and need to eliminate n - 1 teams to have 1 winner remaining, and each match eliminates precisely one team.

Intuition

Let's think about what happens in each match. No matter how the tournament is structured, every single match has exactly one winner and one loser. The loser is eliminated from the tournament, while the winner continues.

To find a champion from n teams, we need to eliminate exactly n - 1 teams (leaving just 1 winner). Since each match eliminates exactly one team, we need exactly n - 1 matches total.

This insight holds true regardless of whether we have even or odd numbers of teams in any round. The special rules about giving byes when there's an odd number of teams don't change the fundamental fact that:

• We start with n teams
• We end with 1 team
• We eliminate n - 1 teams along the way
• Each match eliminates exactly 1 team
• Therefore, we need n - 1 matches

We can verify this with a simple example: if we have 4 teams, we need 2 matches in the first round (eliminating 2 teams) and 1 match in the final (eliminating 1 more team), giving us 3 total matches, which equals 4 - 1.

Learn more about Math patterns.

Solution Approach

The implementation is remarkably straightforward once we understand the mathematical relationship. Since we've established that the total number of matches equals n - 1, the solution becomes a single-line calculation:

class Solution:
    def numberOfMatches(self, n: int) -> int:
        return n - 1

This direct approach leverages the mathematical insight that in any single-elimination tournament:

• Starting teams: n
• Teams to eliminate: n - 1
• Matches needed: n - 1 (since each match eliminates exactly one team)

The beauty of this solution is that we don't need to simulate the tournament round by round. We don't need loops to handle even/odd cases separately, nor do we need to track which teams get byes. The fundamental counting principle gives us the answer directly.

Time Complexity: O(1) - We perform a single arithmetic operation.

Space Complexity: O(1) - We only use a constant amount of extra space.

This solution demonstrates how understanding the underlying mathematical structure of a problem can lead to an elegant solution that bypasses the need for complex simulation logic.

Example Walkthrough

Let's walk through a tournament with 7 teams to see how the solution works:

Round 1: We have 7 teams (odd number)

• 1 team gets a bye (advances automatically)
• 6 teams play in 3 matches
• Teams eliminated: 3
• Teams advancing: 4 (3 winners + 1 bye)

Round 2: We have 4 teams (even number)

• All 4 teams play in 2 matches
• Teams eliminated: 2
• Teams advancing: 2

Round 3 (Final): We have 2 teams (even number)

• Both teams play in 1 match
• Teams eliminated: 1
• Teams advancing: 1 (the champion!)

Total matches played: 3 + 2 + 1 = 6 matches

Now let's verify this with our solution approach:

• Started with: 7 teams
• Ended with: 1 team
• Teams eliminated: 7 - 1 = 6 teams
• Since each match eliminates exactly 1 team: 6 matches needed

The key insight is that regardless of how we pair teams or give byes, we're always eliminating exactly one team per match. To go from 7 teams down to 1 winner, we must eliminate 6 teams, which requires exactly 6 matches.

This is why the solution return n - 1 works perfectly - it directly calculates the number of eliminations needed, which equals the number of matches played.

Solution Implementation

Time and Space Complexity

The time complexity is O(1) because the function performs a single arithmetic operation (subtraction) regardless of the input size. The calculation n - 1 executes in constant time.

The space complexity is O(1) because the function uses a fixed amount of memory that doesn't scale with the input. It only stores the input parameter n and returns a single integer value without using any additional data structures or recursive calls.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Overcomplicating with Simulation

Many developers instinctively implement a round-by-round simulation, unnecessarily complicating the solution:

Problematic Approach:

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

Why it's problematic:

• Unnecessarily complex with O(log n) time complexity
• More code means more potential for bugs
• Harder to understand and maintain
• Misses the elegant mathematical insight

Pitfall 2: Integer Division Confusion

When attempting to derive the formula, some might incorrectly handle integer division:

Incorrect Mental Model:

# Wrong: Trying to calculate rounds and matches per round
rounds = math.ceil(math.log2(n))
# This doesn't account for byes and odd team counts correctly

Solution: Recognize that tracking rounds separately is unnecessary. The total matches across all rounds always equals n-1.

Pitfall 3: Edge Case Overthinking

Developers might worry about edge cases and add unnecessary validation:

Overcautious Approach:

class Solution:
    def numberOfMatches(self, n: int) -> int:
        if n <= 0:
            return 0
        if n == 1:
            return 0
        if n == 2:
            return 1
        # ... more special cases
        return n - 1

Why it's unnecessary:

• The problem constraints typically guarantee n ≥ 1
• The formula n-1 already handles n=1 correctly (returns 0)
• Adding extra checks clutters the code without adding value

Best Practice Solution:

Trust the mathematical insight. Once you understand that each match eliminates exactly one team, the solution is simply:

return n - 1

This demonstrates that the most elegant solutions often come from understanding the problem's fundamental structure rather than simulating its mechanics.