Count of Matches in Tournament

This problem is about simulating a tournament with particular rules for pairing teams and determining the total number of matches played until a winner is decided.

Approach

  1. Initialize a Counter: Start with a variable, say matches, to keep track of the total number of matches played. Initialize it to 0.

  2. Simulate the Tournament: Repeat the following process as long as there are more than 1 team:

    • Even Number of Teams: If the number of teams is even, pair them and play n / 2 matches. Half the teams will advance to the next round.
    • Odd Number of Teams: If the number of teams is odd, randomly advance one team, and pair the rest. Play (n - 1) / 2 matches, and (n - 1) / 2 + 1 teams advance.
    • Update the Counter: Add the number of matches played in the current round to matches.

  3. Return the Result: Return the total number of matches played, i.e., the value of matches.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def numberOfMatches(self, n: int) -> int:
        matches = 0 # Step 1: Initialize the counter

        while n > 1: # Step 2: Simulate the tournament
            if n % 2 == 0: # Even number of teams
                matches += n // 2
                n = n // 2
            else: # Odd number of teams
                matches += (n - 1) // 2
                n = (n - 1) // 2 + 1

        return matches # Step 3: Return the result

Key Takeaways

  • We use a simple simulation to keep track of the number of matches played.
  • At each round, the number of matches depends on whether the number of teams is even or odd.
  • This solution follows the problem’s rules and provides the correct number of matches played to decide a winner in the given tournament scenario.