Count Of Matches In Tournament - Leetcode Solution

Problem Statement:

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.

Solution:

The solution to this problem is pretty straightforward. We can simulate the given tournament and keep track of the total matches played until we get a winner.

• If the given number of teams n is even, we can keep dividing it by 2 until we get an odd number. At each step, we will add n / 2 (number of matches played in this round) to the total matches played variable. Finally, when we get an odd number, we can add (n - 1) / 2 (number of matches played in the last round) to the total matches played variable and return the total matches played.

• If the given number of teams n is odd, we can directly add (n - 1) / 2 (number of matches played in the first round) to the total matches played variable. Then we can keep dividing n - 1 by 2 until we get 1 team left. At each step, we will add (n - 1) / 2 (number of matches played in this round) to the total matches played variable. Finally, we can return the total matches played.

Here's the Python code implementing the above logic:

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

Time Complexity: O(logn)

Space Complexity: O(1)

We can see that the above solution has a time complexity of O(logn) and a space complexity of O(1). Therefore, this solution is optimal and will pass all the test cases on LeetCode.

1