Count of Matches in Tournament

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.

Example 1:

Input: n = 7 Output: 6 Explanation: Details of the tournament:

• 1st Round: Teams = 7, Matches = 3, and 4 teams advance.
• 2nd Round: Teams = 4, Matches = 2, and 2 teams advance.
• 3rd Round: Teams = 2, Matches = 1, and 1 team is declared the winner.

Total number of matches = 3 + 2 + 1 = 6.

Example 2:

Input: n = 14 Output: 13 Explanation: Details of the tournament:

• 1st Round: Teams = 14, Matches = 7, and 7 teams advance.
• 2nd Round: Teams = 7, Matches = 3, and 4 teams advance.
• 3rd Round: Teams = 4, Matches = 2, and 2 teams advance.
• 4th Round: Teams = 2, Matches = 1, and 1 team is declared the winner.

Total number of matches = 7 + 3 + 2 + 1 = 13.

Constraints:

• 1 <= n <= 200

class Solution {
    public int numberOfMatches(int n) {
        int 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;
    }
}

Naive Approach

The most straightforward approach is to simulate the tournament round by round, keeping track of the number of matches played and the number of teams advancing to the next round until only one team remains. This is exactly what the problem description suggests.

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

Optimal Approach

A more efficient approach is to realize that every team except the winner must lose exactly one match. Therefore, the total number of matches played is simply the number of teams minus one.

class Solution {
    public int numberOfMatches(int n) {
        return n - 1;
    }
}

Big(O) Runtime Analysis

• Naive Approach:
  • The while loop iterates until n becomes 1. In each iteration, n is roughly halved. Therefore, the number of iterations is logarithmic with base 2, i.e., O(log n).
  • Inside the loop, the operations are constant time operations.
  • Overall, the time complexity is O(log n).
• Optimal Approach:
  • The optimal solution directly returns n - 1. This is a constant-time operation, so the time complexity is O(1).

Big(O) Space Usage Analysis

• Naive Approach:
  • The space used is constant regardless of the input n. Only a few integer variables are used.
  • Therefore, the space complexity is O(1).
• Optimal Approach:
  • The optimal solution uses a constant amount of space. Only a few integer variables are used.
  • Therefore, the space complexity is O(1).

Edge Cases

1. n = 1:
   • If there is only one team, no matches are played, and the function should return 0. Both solutions will correctly handle this case.
2. n = 2:
   • If there are two teams, one match is played, and the function should return 1. Both solutions will correctly handle this case.
3. Large n (n = 200):
   • For the given constraints (1 <= n <= 200), the iterative approach performs very quickly. For larger values of n, the O(1) solution is preferable, but for this range, either are acceptable.

Both the naive and optimal solutions effectively cover all edge cases. The optimal solution, however, stands out due to its simplicity and efficiency, reflected in its O(1) time complexity. This makes it superior in terms of performance, especially when dealing with a large number of teams.