algoadvance

Leetcode 1688. Count of Matches in Tournament

Problem Statement

You are given an integer n, the number of teams in a tournament. A match is held between two teams, and the winner of each match proceeds to the next round. The process continues until there is only one team remaining. You need to determine and return the total number of matches played in the tournament until a winner is decided.

Clarifying Questions

  1. Is the number of teams always even?
    • No, the number of teams can be either odd or even.
  2. How do matches proceed if there is an odd number of teams in a round?
    • If there is an odd number of teams, one team automatically advances to the next round without playing a match.
  3. Can n be zero or negative?
    • No, the smallest number of teams will be 1, which means n >= 1.

Strategy

The strategy to solve this is straightforward:

  1. You repeatedly divide the number of teams by 2 to get the number of matches in each round.
  2. If the count of teams is odd, one team gets a bye and the total number of teams is reduced by 1 before further processing.
  3. Count all these matches until there is only one team left.

For every round:

Code

Here is how you can implement this in C++:

class Solution {
public:
    int numberOfMatches(int n) {
        int totalMatches = 0;
        
        while (n > 1) {
            if (n % 2 == 0) {
                totalMatches += n / 2;
                n /= 2;
            } else {
                totalMatches += (n - 1) / 2;
                n = (n - 1) / 2 + 1;
            }
        }
        
        return totalMatches;
    }
};

Explanation

  1. Initialize totalMatches to 0.
  2. Use a loop that continues until only one team remains (n > 1).
  3. For each iteration:
    • If the number of teams n is even, add n / 2 to totalMatches and update n to n / 2.
    • If the number of teams n is odd, add (n - 1) / 2 to totalMatches and update n to (n - 1) / 2 + 1.
  4. Return totalMatches after exiting the loop.

Time Complexity

The time complexity of this approach is O(log n) because in each round, the number of teams is approximately halved. Thus, the number of iterations of the loop is logarithmic with respect to n.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI