Count of Matches in Tournament

Easy
542.

Count of Matches in Tournament

Count of Matches in Tournament is an easy coding problem on math and simulation, asked in Amazon and TCS interviews.

A tournament starts with n teams and runs in rounds:

  • If the current number of teams is even, they pair up: n/2 matches are played and n/2 teams advance.
  • If it is odd, one team gets a bye: (n-1)/2 matches are played and (n-1)/2 + 1 teams 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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var numberOfMatches = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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/2 matches are played and n/2 teams advance.
  • If it is odd, one team gets a bye: (n-1)/2 matches are played and (n-1)/2 + 1 teams 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

  1. Hint 1

    Simulating the rounds works, but try tracking what each match accomplishes.

  2. Hint 2

    Every match eliminates exactly one team, and byes eliminate nobody.

  3. Hint 3

    To go from n teams to 1 winner, exactly n - 1 teams 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

  1. Observe that a match always eliminates one team.
  2. The tournament ends with 1 team standing, so n - 1 teams are eliminated in total.
  3. 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 = 1 must answer 0, which n - 1 handles.

Reference solution

Python

def numberOfMatches(n: int) -> int:
    return n - 1

Java

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.

All 337 math problems · the whole catalogue