LeetCode 1688 - Count of Matches in Tournament
The problem describes a tournament where teams compete until only one winner remains. At every round, teams are paired t
Difficulty: 🟢 Easy
Topics: Math, Simulation
Solution
Problem Understanding
The problem describes a tournament where teams compete until only one winner remains. At every round, teams are paired to play matches, but the tournament follows slightly unusual rules depending on whether the current number of teams is even or odd.
If the number of teams is even, every team gets paired with another team. Since each match eliminates exactly one team, there are n / 2 matches and n / 2 teams move to the next round.
If the number of teams is odd, one team automatically advances without playing a match, while the remaining teams are paired up. In this case, (n - 1) / 2 matches are played, and (n - 1) / 2 + 1 teams continue to the next round.
The input consists of a single integer n, representing the number of teams at the beginning of the tournament. The expected output is the total number of matches played until only one team remains.
The constraints are very small, 1 <= n <= 200, which tells us that even a direct simulation would easily fit within time limits. Since the number of teams shrinks every round, the process is naturally efficient.
There are several important edge cases to consider upfront. If n = 1, there is already a winner, so no matches should be played. If n = 2, exactly one match determines the champion. Odd values of n require careful handling because one team advances automatically, which can lead to off by one mistakes in updating the remaining team count.
Approaches
Brute Force Approach
A straightforward approach is to simulate the tournament exactly as described.
We repeatedly process rounds until only one team remains. For each round, we determine whether the number of teams is even or odd. If it is even, we add n / 2 matches to the answer and reduce the number of teams to n / 2. If it is odd, we add (n - 1) / 2 matches and update the number of teams to (n - 1) / 2 + 1.
This works because it directly mirrors the tournament rules. Every round is simulated exactly, and the total number of matches accumulates correctly.
Although this is sometimes called brute force, it is already efficient because the number of teams decreases after every round. Since n <= 200, performance is never a concern.
Optimal Approach
There is an important mathematical observation that makes the problem even simpler.
Every match eliminates exactly one team. Since the tournament starts with n teams and ends with exactly one winner, exactly n - 1 teams must be eliminated.
Because each match removes one team, the total number of matches must also be n - 1.
This means we do not need to simulate the tournament at all. We can directly return n - 1.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(log n) | O(1) | Simulates each tournament round until one team remains |
| Optimal | O(1) | O(1) | Uses the observation that every match eliminates exactly one team |
Algorithm Walkthrough
The optimal algorithm is extremely concise because it relies on a mathematical property of elimination tournaments.
- Observe that every match removes exactly one team from the tournament.
- Notice that the tournament starts with
nteams and ends when exactly one winner remains. - Since only one team survives, exactly
n - 1teams must be eliminated. - Because each match eliminates one team, the total number of matches must equal the number of eliminated teams.
- Return
n - 1.
Why it works
The key invariant is that each match eliminates exactly one team. Regardless of whether a round contains an even or odd number of teams, every match reduces the total number of teams by one. Since we begin with n teams and must end with exactly one, exactly n - 1 eliminations occur, which means exactly n - 1 matches are played.
Python Solution
class Solution:
def numberOfMatches(self, n: int) -> int:
return n - 1
The implementation is intentionally simple because the mathematical observation completely removes the need for simulation.
The method receives the initial number of teams n. Since every match eliminates one team and the tournament ends with one winner, the total number of matches is simply the number of eliminated teams, which equals n - 1.
This implementation directly follows the reasoning from the algorithm walkthrough and runs in constant time.
Go Solution
func numberOfMatches(n int) int {
return n - 1
}
The Go implementation is identical in logic to the Python version. Since the constraints are very small and integer overflow is impossible for values up to 200, a standard int type is sufficient.
There are no slice, array, or memory management concerns because the solution only performs a single arithmetic operation.
Worked Examples
Example 1
Input: n = 7
We apply the mathematical observation.
| Step | Teams Remaining | Eliminations So Far | Matches So Far |
|---|---|---|---|
| Start | 7 | 0 | 0 |
| End Goal | 1 | 6 | 6 |
Since we need to reduce the tournament from 7 teams to 1 winner, exactly 6 teams must be eliminated.
Each match eliminates exactly one team.
Therefore:
Matches = 7 - 1 = 6
Output: 6
For comparison, the simulated tournament would look like this:
| Round | Teams | Matches Played | Teams Advancing |
|---|---|---|---|
| 1 | 7 | 3 | 4 |
| 2 | 4 | 2 | 2 |
| 3 | 2 | 1 | 1 |
Total matches:
3 + 2 + 1 = 6
Example 2
Input: n = 14
Again, we apply the same observation.
| Step | Teams Remaining | Eliminations So Far | Matches So Far |
|---|---|---|---|
| Start | 14 | 0 | 0 |
| End Goal | 1 | 13 | 13 |
To determine a winner, 13 teams must be eliminated.
Since each match eliminates exactly one team:
Matches = 14 - 1 = 13
Output: 13
The simulation confirms this:
| Round | Teams | Matches Played | Teams Advancing |
|---|---|---|---|
| 1 | 14 | 7 | 7 |
| 2 | 7 | 3 | 4 |
| 3 | 4 | 2 | 2 |
| 4 | 2 | 1 | 1 |
Total matches:
7 + 3 + 2 + 1 = 13
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(1) | Only one arithmetic operation is performed |
| Space | O(1) | No extra memory proportional to input size is used |
The algorithm runs in constant time because it does not simulate rounds or iterate over teams. It simply computes n - 1, which takes the same amount of work regardless of the input size. Space usage is also constant because only a single integer calculation is performed.
Test Cases
solution = Solution()
assert solution.numberOfMatches(7) == 6 # Example case with odd teams
assert solution.numberOfMatches(14) == 13 # Example case with even teams
assert solution.numberOfMatches(1) == 0 # Boundary case, already a winner
assert solution.numberOfMatches(2) == 1 # Smallest tournament with a match
assert solution.numberOfMatches(3) == 2 # Odd number with one bye
assert solution.numberOfMatches(4) == 3 # Power of two
assert solution.numberOfMatches(5) == 4 # Odd team count
assert solution.numberOfMatches(8) == 7 # Multiple even rounds
assert solution.numberOfMatches(15) == 14 # Larger odd input
assert solution.numberOfMatches(200) == 199 # Maximum constraint
| Test | Why |
|---|---|
n = 7 |
Validates the provided odd-number example |
n = 14 |
Validates the provided even-number example |
n = 1 |
Tests the minimum boundary case |
n = 2 |
Verifies the simplest possible match |
n = 3 |
Ensures odd-number advancement logic works |
n = 4 |
Checks a clean power-of-two tournament |
n = 5 |
Validates another odd-sized tournament |
n = 8 |
Tests repeated even reductions |
n = 15 |
Confirms larger odd input behavior |
n = 200 |
Verifies correctness at maximum constraint |
Edge Cases
One important edge case is n = 1. In this situation, the tournament already has a winner before any matches are played. A naive simulation might accidentally enter a loop or incorrectly subtract one round. The implementation handles this naturally because 1 - 1 = 0, which correctly indicates no matches are needed.
Another important case is an odd number of teams, such as n = 3 or n = 7. A simulation based solution could easily make mistakes when calculating the advancing team count after a bye. For example, forgetting to include the automatically advancing team could lead to an incorrect total. The mathematical solution avoids this issue entirely because it does not care about round structure, only eliminations.
A third edge case is the maximum constraint, n = 200. While this value is small, it is still useful to verify correctness near the upper bound. Some implementations may unnecessarily simulate rounds or use extra memory. The provided solution remains constant time and constant space regardless of input size, making it robust even at the limit.