We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count of Matches in Tournament

Difficulty: Easy

Problem Description

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 in the tournament, 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.

Key Insights

  • The number of matches played is determined by whether the current number of teams is even or odd.
  • If n is even, n / 2 matches are played.
  • If n is odd, (n - 1) / 2 matches are played, with one team automatically advancing.
  • This process continues until only one team remains, at which point the tournament is over.
  • We can simulate this process in a loop until we reach the final winner.

Space and Time Complexity

Time Complexity: O(log n) - The number of rounds is logarithmic with respect to n. Space Complexity: O(1) - We are using a constant amount of space.

Solution

To solve this problem, we can use a simple simulation approach. We will keep track of the number of matches played in a variable. In each round, we check if the number of teams is even or odd. We then calculate the number of matches for that round and update the number of teams for the next round accordingly. We continue this process until only one team remains, at which point we return the total number of matches played.

Code Solutions

def numberOfMatches(n: int) -> int:
    matches = 0
    while n > 1:
        if n % 2 == 0:  # n is even
            matches += n // 2
            n = n // 2  # half the teams advance
        else:  # n is odd
            matches += (n - 1) // 2
            n = (n - 1) // 2 + 1  # one team advances automatically
    return matches
← Back to All Questions