1688. Count of Matches in Tournament
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 81.5%
Problem Breakdown
The problem involves determining the total number of matches played in a tournament until a winner is decided. The tournament has n teams, and the rules for pairing teams are:
- If
nis even, each team gets paired with another team, resulting inn / 2matches andn / 2teams advancing. - If
nis odd, one team randomly advances, and the rest get paired, resulting in(n - 1) / 2matches and(n - 1) / 2 + 1teams advancing.
The input is an integer n, representing the number of teams. The output should be the total number of matches played until one team remains as the winner. Constraints are 1 <= n <= 200.
Intuition
A brute-force approach would simulate each round of the tournament, counting matches and advancing teams until only one team is left. However, this approach is inefficient in terms of both time and space complexity.
The key insight is to recognize that every match eliminates exactly one team. Therefore, to determine a winner from n teams, we need to eliminate n - 1 teams, which requires n - 1 matches. This observation leads to a simple and efficient solution.
Approach
We can directly return n - 1 as the number of matches played in the tournament. This approach leverages the insight that each match eliminates one team, and we need to eliminate n - 1 teams to determine a winner.
Complexity Analysis
- Time Complexity: O(1), since the solution involves a constant-time calculation.
- Space Complexity: O(1), as no additional space is required beyond a few variables.
Solution
def numberOfMatches(n: int) -> int:
return n - 1
Edge Cases Handled
- n = 1: Only one team, so no matches are played. The function returns
0, which is correct. - n = 2: Two teams, resulting in one match. The function returns
1, which is correct. - n = 3: Three teams, resulting in two matches (one random advance). The function returns
2, which is correct. - n = 4: Four teams, resulting in two matches. The function returns
3, which is correct. - n = 7: Seven teams, as described in Example 1. The function returns
6, which is correct. - n = 14: Fourteen teams, as described in Example 2. The function returns
13, which is correct.
This solution handles all edge cases efficiently and correctly, leveraging the insight that each match eliminates one team until only one team remains.