Domain 1EasyCORE

Count of Matches in Tournament

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 `n` is even, each team gets paired with another team, resulting in `n / 2` matches and `n / 2` teams advancing. - If `n` is odd, one team randomly advances, and the rest get paired, resulting in `(n - 1) / 2` matches and `(n - 1) / 2 + 1` teams advancing.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 0

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 n is even, each team gets paired with another team, resulting in n / 2 matches and n / 2 teams advancing.
  • If n is odd, one team randomly advances, and the rest get paired, resulting in (n - 1) / 2 matches and (n - 1) / 2 + 1 teams 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.