💬 Discord
Sign In
NeetCode #890LC-1688EasyMath & Geometry
← Back to All Problems

#890 · #1688 · Count of Matches in Tournament(比赛中的配对次数)

📌 Problem Statement & Constraints

In a tournament with n teams, teams are paired each round; the winner advances and the loser is eliminated, until a single champion remains. Return the total number of matches played. Constraints: 1 <= n <= 200.

💡 Core Algorithmic Approaches

  1. Every match eliminates exactly one team from the tournament.
  2. Starting with n teams and finishing with 1 champion means n - 1 teams are eliminated in total.
  3. Therefore exactly n - 1 matches are played, no matter how the pairings are arranged.
  4. This is an O(1) invariant argument; simulating the rounds would be O(log n) and unnecessary.

💻 Benchmark Python3 Implementation

class Solution:
    def numberOfMatches(self, n: int) -> int:
        # each match eliminates one team; n teams -> n - 1 eliminations
        return n - 1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1).
💾 Space Complexity
O(1).

⚠️ Interview Pitfalls & Follow-ups

  • Simulating round by round: correct but O(log n); the elimination invariant gives the answer immediately.
  • Handling byes incorrectly in a simulation: an odd team count leaves one team unpaired, which is exactly the complication the invariant avoids.
  • Returning n: the champion is never eliminated, so the count is n - 1.
  • Assuming n is a power of two: the invariant holds for every n.