Count of Matches in Tournament
EasyPrompt
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 / 2matches are played, andn / 2teams 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) / 2matches are played, and(n - 1) / 2 + 1teams 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
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a variable
totalMatchesto 0. - Use a loop that continues as long as the number of teams,
n, is greater than 1. - Inside the loop, check if
nis even or odd. - If
nis even, calculate matches for the round asn / 2. Add these matches tototalMatches. Updatenton / 2for the next round. - If
nis odd, calculate matches as(n - 1) / 2. Add these tototalMatches. Updatento(n - 1) / 2 + 1for the next round. - Once the loop finishes (when
nis 1), returntotalMatches.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- The goal of the tournament is to find a single winner from
nteams. - To have one winner,
n - 1teams 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 - 1teams isn - 1. - The function can simply return
n - 1.
Walkthrough
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.
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; }}Complexity
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`.
Trade-offs
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.
Solutions
Solution
class Solution {public int numberOfMatches(int n) { return n - 1; }}/** * @param {number} n * @return {number} */ var numberOfMatches = function ( n,) { return n - 1;};class Solution {public: int numberOfMatches(int n) { return n - 1; }};class Solution: def numberOfMatches(self, n: int) -> int: return n - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.