Count of Matches in Tournament (LeetCode 1688): Simulate It, Then Notice the One

Author: ad2c0706ff

04 November 2026

Views: 7

The problem: a tournament starts with `n` teams. In each round, if the number of teams is even, they pair up, play `n / 2` matches, and `n / 2` teams advance. If it is odd, one team gets a bye, `(n - 1) / 2` matches are played, and `(n - 1) / 2 + 1` teams advance. Return the total number of matches played until a winner is decided.

Example: `n = 7`. Round 1: 3 matches, 4 teams advance. Round 2: 2 matches, 2 advance. Round 3: 1 match. Total 6.

## Step 1: simulate exactly what the prompt says

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

The loop runs about log2(n) times, so this is O(log n) time and O(1) space. Writing this first is a good habit: it is obviously correct because it mirrors the rules.

## Step 2: the observation

Every match eliminates exactly one team. The tournament ends when n - 1 teams have been eliminated. So the answer is always `n - 1`.

```python
def numberOfMatches(n):
return n - 1
```

Check it on the example: 7 - 1 = 6. It matches.

## How to talk about it in an interview

- Lead with the simulation if you don't see the trick immediately; it shows you can turn rules into code.
- Then say why the count of something "per step" can often be replaced by an invariant. Here the invariant is "one match removes one team".
- The same reasoning answers "how many comparisons does a knockout-style max-finding take?" (n - 1) and is the start of the classic "find the second largest in n + log n - 2 comparisons" question.

## Edge cases

- `n = 1`: no matches, the formula gives 0.
- Large n: both versions avoid overflow in Python; in Java or C++ an int is plenty for the constraint (n <= 200).

If you want to practise explaining invariants like this under time pressure, I work on an AI interview copilot (https://www.linkjob.ai/interview-copilot/) at Linkjob AI that gives real-time hints in mock rounds. (Disclosure: affiliated.)


Edit Code:

Please enter an edit code

Edit codes must be at least 20 characters

Share