1688. Count of Matches in Tournament

📝 Problem Details

• Title: 1688. Count of Matches in Tournament
• Link: https://leetcode.com/problems/count-of-matches-in-tournament/
• Difficulty: Easy
• Tags/Categories: {{tags/categories}}

💭What Were My Initial Thoughts?

The number of matches directly corresponds to the number of eliminations. Since one match eliminates one team, the total number of matches for nnn teams is 

Matches = n - 1

this formula holds regardless of whether n is even or odd

🤔What Did I Struggle With?

~

💡 Explanation of Solution

Tournament Simulation:
- If n is even:
	- All teams are paired into n/2 matches.
    - After these matches, n/2 teams advance.

- If n is odd:
    - (n−1)/2 matches are played with n−1 teams.
    - The remaining unpaired team automatically advances to the next round.

- Repeat until only one team remains.

⌛ Complexity Analysis

Time Complexity:
- Simulation: O(log⁡n), as n halves in each iteration.
- Optimized: O(1), direct computation.

Space Complexity:
- Both approaches: O(1)

💻 Implementation of Solution

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

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