Count of Matches in Tournament solution and explanation
Google
9 more videos on this problem
Count of Matches in Tournament | MICROSOFT | Leetcode 1688codestorywithMIK · 12:09 · 7K views
Count of Matches in Tournament - Leetcode 1688 - PythonNeetCodeIO · 8:46 · 4K views
1688. Count of Matches in Tournament || LeetcodeAryan Mittal · 3:59 · 1K views
Count of Matches In Tournament LeetCode Solution Java (leetcode 1688)Engineering Digest · 6:30 · 1K views
Leetcode 1688. Count of Matches in TournamentFraz · 2:55 · 917 views
1688. Count of Matches in Tournament (Leetcode Easy)Programming Live with Larry · 2:50 · 471 views
Count of Matches in Tournament | LeetCode 1688 | CppCodeClips with Abhishek Ranjan · 5:11 · 253 views
How to Solve "1688 Count of Matches in Tournament" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 5:19 · 252 views
Solving LeetCode 1688 Count of Matches in Tournament | Math | Adobe | Yahoo | EasyCode Harmony · 7:23 · 217 views
Leetcode 1688 - Count of Matches in TournamentTintin And Codes · 12:03 · 136 views
The 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 / 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
Approach overview
Problem Overview: You are given n teams in a knockout tournament. Each round pairs teams to play matches, and the winner advances to the next round. If the number of teams is odd, one team automatically advances. The goal is to count the total number of matches played until a single champion remains.
Approach 1: Iterative Reduction Approach (Simulation) (Time: O(log n), Space: O(1))
This method directly simulates how the tournament progresses. In each round, compute how many matches are played based on the number of teams. If n is even, n / 2 matches occur and n / 2 teams advance. If n is odd, (n - 1) / 2 matches occur and one team automatically advances, leaving (n - 1) / 2 + 1 teams for the next round. Repeat this process using a loop until only one team remains, accumulating the total number of matches along the way. This is a straightforward simulation approach that mirrors the real tournament structure and is useful when practicing iterative reasoning problems.
Approach 2: Direct Mathematical Calculation (Time: O(1), Space: O(1))
The key insight comes from observing what happens in every match: exactly one team is eliminated. Starting with n teams and ending with one champion means n - 1 teams must be eliminated. Since each match eliminates exactly one team, the total number of matches played must be n - 1. This eliminates the need for simulation entirely. The result can be returned immediately with a simple formula. This solution relies on basic math reasoning rather than step‑by‑step iteration, making it the most efficient and elegant approach.
Recommended for interviews: Start with the simulation approach to show you understand how the tournament rounds work. Then present the mathematical insight that each match removes one team, leading to the formula n - 1. Interviewers typically expect the constant-time math solution because it demonstrates problem simplification and analytical thinking.
Approach 1: Iterative Reduction Approach
This approach involves treating the tournament rounds as iterative events where in each round, the number of matches is calculated, and non-advanced teams are eliminated until one team remains. This approach iterates over the number of teams until a winner is decided by subtracting the number of matches played from the total count of teams.
def number_of_matches(n):
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
n = 7
print(number_of_matches(n)) # Output: 6public class Tournament {
public static 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;
}
public static void main(String[] args) {
int n = 7;
System.out.println(numberOfMatches(n)); // Output: 6
}
}#include <iostream>
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;
}
int main() {
int n = 7;
std::cout << numberOfMatches(n) << std::endl; // Output: 6
return 0;
}function numberOfMatches(n) {
let 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;
}
let n = 7;
console.log(numberOfMatches(n)); // Output: 6#include <stdio.h>
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;
}
int main() {
int n = 7;
printf("%d\n", numberOfMatches(n)); // Output: 6
return 0;
}using System;
public class Tournament {
public static 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;
}
public static void Main() {
int n = 7;
Console.WriteLine(NumberOfMatches(n)); // Output: 6
}
}The Python solution is similar and follows the iterative process to compute matches by changing the number of teams until one remains. This approach efficiently uses integer division and conditional logic to handle odd and even cases.
Time Complexity: O(log n)
Space Complexity: O(1)
Approach 2: Direct Mathematical Calculation
Instead of simulating each round, this approach uses the observation that to find a winner among n teams, exactly n - 1 matches must be played. This is because each match eliminates exactly one team and n - 1 eliminations leave one champion.
def number_of_matches(n):
return n - 1
n = 7
print(number_of_matches(n)) # Output: 6public class Tournament {
public static int numberOfMatches(int n) {
return n - 1;
}
public static void main(String[] args) {
int n = 7;
System.out.println(numberOfMatches(n)); // Output: 6
}
}#include <iostream>
int numberOfMatches(int n) {
return n - 1;
}
int main() {
int n = 7;
std::cout << numberOfMatches(n) << std::endl; // Output: 6
return 0;
}function numberOfMatches(n) {
return n - 1;
}
let n = 7;
console.log(numberOfMatches(n)); // Output: 6#include <stdio.h>
int numberOfMatches(int n) {
return n - 1;
}
int main() {
int n = 7;
printf("%d\n", numberOfMatches(n)); // Output: 6
return 0;
}using System;
public class Tournament {
public static int NumberOfMatches(int n) {
return n - 1;
}
public static void Main() {
int n = 7;
Console.WriteLine(NumberOfMatches(n)); // Output: 6
}
}In Python, the solution simply returns n - 1, which is the necessary number of matches to reduce the teams to one winner.
Time Complexity: O(1)
Space Complexity: O(1)
Approach 3: Quick Thinking
From the problem description, we know that there are n teams in total. Each pairing will eliminate one team. Therefore, the number of pairings is equal to the number of teams eliminated, which is n - 1.
The time complexity is O(1), and the space complexity is O(1).
function numberOfMatches(n: number): number {
return n - 1;
}func numberOfMatches(n int) int {
return n - 1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Reduction Approach | Time Complexity: O(log n) |
| Direct Mathematical Calculation | Time Complexity: O(1) |
| Quick Thinking | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Reduction (Simulation) | O(log n) | O(1) | When you want to simulate tournament rounds or demonstrate step-by-step reasoning |
| Direct Mathematical Calculation | O(1) | O(1) | Best choice when recognizing that each match eliminates exactly one team |
Frequently asked questions
Is Count of Matches in Tournament easy or hard?
Count of Matches in Tournament is classified as an Easy problem. The simulation approach is straightforward, and the key insight that the answer is always n - 1 makes the optimal solution extremely simple.
Count of Matches in Tournament Python/Java solution
In Python or Java, the optimal implementation returns n - 1 directly. The simulation version repeatedly computes matches per round using division and updates the number of teams until only one remains.
How to solve Count of Matches in Tournament in O(1)?
Use the observation that every match removes exactly one team from the tournament. To reduce n teams down to a single winner, exactly n - 1 teams must be eliminated. Therefore, the number of matches played is simply n - 1.
What is the best approach for Count of Matches in Tournament?
The best approach is the direct mathematical observation that every match eliminates exactly one team. Starting with n teams and ending with one champion means n - 1 teams are eliminated, so the total number of matches must be n - 1. This gives an O(1) time and O(1) space solution.
Is Count of Matches in Tournament asked at Google/Amazon/Meta?
Problems based on mathematical reasoning and tournament elimination logic appear in interviews at companies like Amazon, Google, and Meta. While this specific question is easy, it tests whether candidates can simplify a simulation problem into a direct mathematical formula.
What data structure is used in Count of Matches in Tournament?
No special data structure is required. The problem relies on simple arithmetic and reasoning. A simulation version uses basic variables and loops, while the optimal solution uses a direct mathematical formula.
What is the time complexity of Count of Matches in Tournament?
The optimal mathematical solution runs in O(1) time and O(1) space because the result is computed directly as n - 1. A simulation approach that models each tournament round takes O(log n) time since the number of teams roughly halves each round.