Count of Matches in Tournament

Difficulty: Easy | Acceptance: 86.40% | Paid: No Topics: Math, Simulation

You are given an integer n, the number of teams in a tournament that has strange rules:

• If the current number of teams is even, each team gets paired with another team. A total of n / 2 matches are played, and n / 2 teams advance to the next round.
• If the current number of teams is odd, one team randomly advances, and the rest gets paired. A total of (n - 1) / 2 matches are played, and (n - 1) / 2 + 1 teams advance to the next round.

Return the number of matches played in the tournament until a winner is decided.

• Examples
• Constraints
• Simulation Approach
• Mathematical Approach

Examples

Example 1

Input: n = 7
Output: 6
Explanation:
- Round 1: 7 teams, 3 matches, 4 teams advance.
- Round 2: 4 teams, 2 matches, 2 teams advance.
- Round 3: 2 teams, 1 match, 1 team wins.
Total matches = 3 + 2 + 1 = 6.

Example 2

Input: n = 14
Output: 13
Explanation:
- Round 1: 14 teams, 7 matches, 7 teams advance.
- Round 2: 7 teams, 3 matches, 4 teams advance.
- Round 3: 4 teams, 2 matches, 2 teams advance.
- Round 4: 2 teams, 1 match, 1 team wins.
Total matches = 7 + 3 + 2 + 1 = 13.

Constraints

1 <= n <= 200

Simulation

Intuition Simulate the tournament round by round, counting matches in each round until only one team remains.

Steps

• Initialize matches counter to 0
• While n > 1:
  • If n is even, add n/2 to matches and set n = n/2
  • If n is odd, add (n-1)/2 to matches and set n = (n-1)/2 + 1
• Return matches

class Solution:
    def numberOfMatches(self, n: int) -> int:
        matches = 0
        while n > 1:
            if n % 2 == 0:
                matches += n // 2
                n = n // 2
            else:
                matches += (n - 1) // 2
                n = (n - 1) // 2 + 1
        return matches

Complexity

• Time: O(log n) - number of rounds is logarithmic
• Space: O(1) - only using constant extra space
• Notes: Straightforward simulation but not the most efficient

Mathematical

Intuition In a single-elimination tournament, every match eliminates exactly one team. To find one winner from n teams, n-1 teams must be eliminated, so n-1 matches are needed.

Steps

• Simply return n - 1

class Solution:
    def numberOfMatches(self, n: int) -> int:
        return n - 1

Complexity

• Time: O(1) - constant time operation
• Space: O(1) - constant space
• Notes: Optimal solution with elegant mathematical insight