Leetcode – Count of Matches in Tournament Solution

The “Count of Matches in Tournament” problem on Leetcode is a fascinating problem that tests your understanding of basic mathematics and algorithmic logic. This problem appears simple but effectively examines how well you can optimize your code for performance and readability. In this guide, we will explore various ways to tackle this problem, dig into their time and space complexities.

Problem Statement

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

1. 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.
2. 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.

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

Example

Input: n = 7
Output: 6

Basic Approach: Loop Iteration

The naive or brute-force approach is to simulate the tournament by keeping track of the number of teams and the matches played in each round.

Python Code

def numberOfMatches(n):
    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

Time Complexity

The time complexity is O(log⁡ n), because we are essentially halving the number of teams at each step, and the number of operations is proportional to the number of times n can be halved until it becomes 1.

Optimized Approach: Mathematical Solution

The problem can also be solved mathematically. It can be observed that irrespective of the number of teams being odd or even, the total number of matches that would be played to determine a winner is always n−1.

Python Code

def numberOfMatches(n):
    return n - 1

Time Complexity

The time complexity of this approach is O(1), as we just perform a single arithmetic operation.

Testing Your Solution

Before you submit your code on Leetcode, you should test it against some test cases to ensure its correctness.

assert numberOfMatches(7) == 6
assert numberOfMatches(14) == 13
assert numberOfMatches(11) == 10
assert numberOfMatches(2) == 1

Conclusion

The “Count of Matches in Tournament” problem seems straightforward but provides a good test of basic programming logic and mathematical understanding. By exploring both the simulation and mathematical approaches, you can see how critical thinking and a deep understanding of the problem can result in a much more efficient solution.