# Count of Matches in Tournament
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-of-matches-in-tournament)
Canonical: https://scaleengineer.com/dsa/problems/count-of-matches-in-tournament
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
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`

# Approaches
## Iterative Simulation
This approach directly simulates the tournament round by round as described in the problem statement. We maintain a count of the current number of teams and the total matches played. In a loop, we calculate the matches played in the current round and the number of teams advancing to the next round, updating our counts accordingly. The simulation continues until only one team, the winner, remains.
**Time:** O(log n) - In each iteration of the loop, the number of teams `n` is roughly halved. This means the number of rounds (and loop iterations) is logarithmic with respect to the initial number of teams. · **Space:** O(1) - The algorithm uses a fixed number of variables (`totalMatches`, `n`, `matches`), so the space required does not scale with the input size.
**Pros:** It is intuitive and directly translates the problem description into code.; This method would work even if the rules were more complex and didn't have a simple mathematical shortcut.
**Cons:** It is computationally more expensive than the mathematical approach because it involves a loop and conditional checks.; The code is more complex and longer than the optimal solution.
### Explanation
We start with the initial number of teams, `n`, and a total match count initialized to zero. We then enter a `while` loop that continues as long as the number of teams is greater than 1. Inside the loop, we apply the rules of the tournament. If the current number of teams is even, `n / 2` matches are played, and `n / 2` teams advance. We add the matches to our total and update `n`. If the number of teams is odd, `(n - 1) / 2` matches are played, and `(n - 1) / 2 + 1` teams advance. Again, we update the total matches and the value of `n`. The loop terminates when `n` becomes 1, at which point we have found the winner, and we can return the total accumulated matches.

```java
class Solution {
    public int numberOfMatches(int n) {
        int totalMatches = 0;
        while (n > 1) {
            if (n % 2 == 0) {
                // Even number of teams
                int matches = n / 2;
                totalMatches += matches;
                n = n / 2;
            } else {
                // Odd number of teams
                int matches = (n - 1) / 2;
                totalMatches += matches;
                n = (n - 1) / 2 + 1;
            }
        }
        return totalMatches;
    }
}
```
### Algorithm
- Initialize a variable `totalMatches` to 0.
- Use a loop that continues as long as the number of teams, `n`, is greater than 1.
- Inside the loop, check if `n` is even or odd.
- If `n` is even, calculate matches for the round as `n / 2`. Add these matches to `totalMatches`. Update `n` to `n / 2` for the next round.
- If `n` is odd, calculate matches as `(n - 1) / 2`. Add these to `totalMatches`. Update `n` to `(n - 1) / 2 + 1` for the next round.
- Once the loop finishes (when `n` is 1), return `totalMatches`.

## Mathematical Approach
This approach leverages a key insight about elimination tournaments. To determine a single winner from a pool of `n` teams, exactly `n - 1` teams must be eliminated. The rules of this specific tournament state that every match results in exactly one team being eliminated. Therefore, the total number of matches played must be equal to the total number of teams that need to be eliminated.
**Time:** O(1) - The result is calculated with a single subtraction, which is a constant-time operation. · **Space:** O(1) - The solution does not use any extra space that scales with the input `n`.
**Pros:** Extremely efficient, providing the answer in a single operation.; The code is minimal, simple, and elegant.; It avoids loops and conditional logic, making it faster and less prone to errors.
**Cons:** The solution relies on a logical insight that might not be immediately apparent from the problem description.
### Explanation
The fundamental principle of any single-elimination tournament is that each match produces one winner and one loser, effectively eliminating one team. The tournament concludes when only one team remains undefeated. If we start with `n` teams, we need to eliminate `n - 1` of them to be left with a single champion. Since every single match eliminates exactly one team, the total number of matches played must be equal to the number of teams that need to be eliminated. Therefore, the total number of matches is simply `n - 1`. This simple mathematical relationship holds true regardless of how the teams are paired in each round.

```java
class Solution {
    public int numberOfMatches(int n) {
        // To have one winner, n - 1 teams must be eliminated.
        // Each match eliminates exactly one team.
        // Therefore, n - 1 matches must be played in total.
        return n - 1;
    }
}
```
### Algorithm
- The goal of the tournament is to find a single winner from `n` teams.
- To have one winner, `n - 1` teams must be eliminated.
- Observe that each match played, according to the rules, results in the elimination of exactly one team.
- Therefore, the total number of matches required to eliminate `n - 1` teams is `n - 1`.
- The function can simply return `n - 1`.

# Solutions
### Java

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

```

### JavaScript

```javascript
/** * @param {number} n * @return {number} */ var numberOfMatches = function (
  n,
) {
  return n - 1;
};

```

### CPP

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

```

### Python

```python
class Solution:
    def numberOfMatches(self, n: int) -> int: return n - 1

```