Count of Matches in Tournament — Problem & Solution
Count of Matches in Tournament solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Count of Matches in Tournament is an easy coding problem on math and simulation, asked in Amazon and TCS interviews.
- Difficulty: Easy
- Topics: Math, Simulation
- Asked at: Amazon, TCS
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A tournament starts with n teams and runs in rounds:
- If the current number of teams is even, they pair up:
n/2matches are played andn/2teams advance. - If it is odd, one team gets a bye:
(n-1)/2matches are played and(n-1)/2 + 1teams advance.
Return the total number of matches played until one winner remains.
Example 1
Input: n = 7
Output: 6
Explanation: 3 + 2 + 1 = 6 matches across the rounds.
Example 2
Input: n = 14
Output: 13
Example 3
Input: n = 1
Output: 0
Explanation: One team is already the winner.
Constraints
1 <= n <= 200
Hints for Count of Matches in Tournament
Hint 1
Simulating the rounds works, but try tracking what each match accomplishes.
Hint 2
Every match eliminates exactly one team, and byes eliminate nobody.
Hint 3
To go from
nteams to 1 winner, exactlyn - 1teams must be eliminated.
How to solve Count of Matches in Tournament
Count eliminations rather than rounds. Each match removes exactly one team and a bye removes none, so reaching a single winner takes precisely n - 1 matches.
Approach
- Observe that a match always eliminates one team.
- The tournament ends with 1 team standing, so
n - 1teams are eliminated in total. - Return
n - 1.
Why it works
The elimination count is invariant to how the byes fall — whether n is odd or even only affects how the matches are grouped into rounds, never the total. Simulation confirms it: 7 → 3 + 2 + 1 = 6 = 7 - 1.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- Simulating is also correct and O(log n); the closed form is just simpler.
n = 1must answer 0, whichn - 1handles.
Reference solution
Python
def numberOfMatches(n: int) -> int:
return n - 1Java
public static int numberOfMatches(int n) {
return n - 1;
}C++
int numberOfMatches(int n) {
return n - 1;
}JavaScript
var numberOfMatches = function(n) {
return n - 1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.