Count of Matches in Tournament: Every Match Eliminates One

LeetCode 1688. Count of Matches in Tournament gives you n teams and asks you to count the total number of matches played in a single-elimination tournament until one winner remains.

The tournament follows specific rules for each round. If the number of teams is even, every team gets paired up. If the number of teams is odd, one team gets a bye (advances automatically), and the rest pair up. You need to return the total number of matches across all rounds.

The problem

Here are the round-by-round rules:

• Even number of teams: n / 2 matches are played, and n / 2 teams advance.
• Odd number of teams: (n - 1) / 2 matches are played, and (n - 1) / 2 + 1 teams advance (one team gets a bye).

The tournament continues until only one team is left.

The simulation approach

The most direct way to solve this is to simulate the tournament round by round. Start with n teams. In each round, play n // 2 matches, then update n to the number of teams advancing. Keep a running total of matches until n equals 1.

def numberOfMatches(n):
    total = 0
    while n > 1:
        total += n // 2
        n = n // 2 + n % 2
    return total

This works because n // 2 gives the number of matches regardless of whether n is even or odd. The remaining teams are n // 2 winners plus n % 2 (which is 1 if n is odd, giving the bye team, and 0 if even).

The key insight

Here is the observation that turns this into a one-liner: every single match eliminates exactly one team. No exceptions. One match, one loser, one elimination.

To go from n teams down to 1 winner, you need exactly n - 1 eliminations. Since each match contributes exactly one elimination, the total number of matches is always n - 1.

Step-by-step walkthrough

Let's trace through n = 7 to see both the simulation and the invariant in action.

The simulation gives 3 + 2 + 1 = 6. The formula gives 7 - 1 = 6. Same answer, but the formula required zero iteration.

The code

The math approach:

def numberOfMatches(n):
    return n - 1

The simulation approach:

def numberOfMatches(n):
    total = 0
    while n > 1:
        total += n // 2
        n = n // 2 + n % 2
    return total

Both produce the same result for every valid input. The simulation explicitly halves the field each round, accumulating matches. The math approach skips the loop entirely by recognizing the invariant. If you see n - 1 and wonder "why does that work?", trace through a few examples. Every match removes one team, and you need to remove n - 1 teams to crown a single winner.

Complexity analysis

The simulation runs O(log n) rounds because the team count roughly halves each time. The math approach is constant time and constant space.

The building blocks

Invariant reasoning

The core technique here is identifying an invariant: a property that holds true at every step of the process. In this case, the invariant is "each match eliminates exactly one team." Once you see that, the total eliminations needed (and therefore total matches) is fixed at n - 1, regardless of how the rounds play out.

This style of reasoning appears in many problems. Instead of simulating a process step by step, you find a quantity that is conserved or predictable across all steps, and use it to jump directly to the answer.

Simulation vs closed-form

Some problems have both a simulation solution and a closed-form formula. The simulation is usually easier to come up with, since you just translate the problem statement into code. The closed-form requires deeper insight but gives you a faster solution.

When you encounter a simulation problem, always ask: "Is there a pattern in the totals?" or "Is there a conserved quantity?" If the answer is yes, you can often replace the loop with a formula.

Edge cases

• n = 1: Zero matches. There is already a winner. The formula gives 1 - 1 = 0.
• n = 2: One match. Two teams play, one wins. The formula gives 2 - 1 = 1.
• Large n: The formula handles any value instantly. The simulation also works fine since it only runs O(log n) iterations.

From understanding to recall

The key insight to remember for this problem: "one match, one elimination." Once you see that invariant, the answer n - 1 is immediate. You do not need to remember the even/odd branching logic or the simulation loop. You just need the observation that eliminating n - 1 teams requires exactly n - 1 matches.

This kind of invariant thinking is a transferable skill. Many problems that look like they require simulation can be solved in O(1) once you spot the right invariant. Drilling that recognition with spaced repetition ensures it becomes second nature rather than something you have to rediscover each time.

Related posts

• Power of Two - Another problem where understanding a mathematical property gives an O(1) solution instead of simulation.
• Happy Number - Simulation with a termination insight, similar to recognizing when simulation is unnecessary.
• Fibonacci Number - A problem where both simulation (iteration) and closed-form solutions exist.