Count how many matches are played in a knockout tournament until one winner remains.
You are given the number of teams in a single-elimination tournament.
In every round:
- If the number of teams is even, each team is paired with exactly one opponent and every pair plays one match.
- If the number of teams is odd, one team advances to the next round without playing, and the remaining teams are paired normally.
After each round, only the winners continue. The tournament ends when exactly one team remains.
Return the total number of matches played.
Input Format
- A single integer
n, the number of teams.
Output Format
- Return the total number of matches played until one champion remains.
Constraints
- The tournament is single-elimination.
- Exactly one winner advances from each match.
Example 1
Input
n = 7
Output
6
Explanation
A single-elimination tournament must eliminate 6 teams to leave 1 winner, and each match eliminates exactly one team.
Example 2
Input
n = 14
Output
13
Explanation
Every match removes one team. To determine one champion from 14 teams, 13 teams must be eliminated, so 13 matches are played.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.