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.)