Count of Matches in Tournament - Practice Coding Problems

Count of Matches in Tournament - Problem

Math Simulation Easy

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.

Input & Output

Example 1 — Odd Number of Teams

$ Input: n = 7

› Output: 6

💡 Note: Round 1: 7 teams (odd) → 3 matches, 4 teams advance. Round 2: 4 teams (even) → 2 matches, 2 teams advance. Round 3: 2 teams (even) → 1 match, 1 winner. Total: 3 + 2 + 1 = 6 matches.

Example 2 — Even Number of Teams

$ Input: n = 14

› Output: 13

💡 Note: Mathematical insight: each match eliminates exactly 1 team. To go from 14 teams to 1 winner, we eliminate 13 teams, requiring 13 matches.

Example 3 — Minimum Case

$ Input: n = 2

› Output: 1

💡 Note: Only 2 teams need just 1 match to determine the winner. Using formula: n - 1 = 2 - 1 = 1.

Constraints

1 ≤ n ≤ 200

Visualization

Tap to expand

Understanding the Visualization

Input

n teams enter tournament

Process

Each match eliminates exactly 1 team

Output

Total matches = n - 1

Key Takeaway

🎯 Key Insight: Each match eliminates exactly one team, so total matches always equals n-1

Asked in

G Google 15 a Amazon 12

The key insight is that each match eliminates exactly one team. To go from n teams to 1 winner, we need n-1 eliminations, so the answer is always n-1. Best approach uses mathematical reasoning for O(1) solution. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Simulation Approach	O(log n)	O(1)	Simulate the tournament round by round, counting total matches
Mathematical Insight	O(1)	O(1)	Each match eliminates exactly one team, so total matches = n - 1

Simulation Approach — Algorithm Steps

Start with n teams
While more than 1 team remains: count matches in current round
Add matches to total and calculate remaining teams
Return total matches

Visualization

Tap to expand

Step-by-Step Walkthrough

Round 1

7 teams → 3 matches, 4 teams advance

Round 2

4 teams → 2 matches, 2 teams advance

Round 3

2 teams → 1 match, 1 winner

Code -

solution.c — C

#include <stdio.h>

int solution(int n) {
    int totalMatches = 0;
    int teams = n;
    
    while (teams > 1) {
        int matches;
        if (teams % 2 == 0) {
            // Even teams: n/2 matches, n/2 teams advance
            matches = teams / 2;
            teams = teams / 2;
        } else {
            // Odd teams: (n-1)/2 matches, (n-1)/2 + 1 teams advance
            matches = (teams - 1) / 2;
            teams = (teams - 1) / 2 + 1;
        }
        
        totalMatches += matches;
    }
    
    return totalMatches;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

We simulate log n rounds since teams are halved each round

⚡ Linearithmic

Space Complexity

O(1)

Only using a few variables to track teams and matches

✓ Linear Space

35.6K Views

Medium Frequency

~5 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler