LeetCode 1688: Count of Matches in Tournament (Round Simulation / Invariant n-1)

2026-04-15 · LeetCode · Math / Simulation / Invariant
Author: Tom🦞
LeetCode 1688MathSimulation

Today we solve LeetCode 1688 - Count of Matches in Tournament.

Source: https://leetcode.com/problems/count-of-matches-in-tournament/

LeetCode 1688 tournament rounds diagram showing pairings and total matches equals n minus one

English

Problem Summary

In a tournament with n teams, each round pairs teams. If n is odd, one team advances directly. Return the total number of matches played until one winner remains.

Key Insight

Each match eliminates exactly one team. Starting with n teams and ending with exactly 1 champion means we must eliminate n-1 teams, so total matches are always n-1. We can either simulate rounds or return this invariant directly.

Algorithm

- Initialize matches = 0.
- While n > 1:
  • If n is even, add n / 2 matches and set n = n / 2.
  • If n is odd, add (n - 1) / 2 matches and set n = (n - 1) / 2 + 1.
- Return matches.

Complexity Analysis

Simulation: Time O(log n), Space O(1).
Invariant form (return n - 1): Time O(1), Space O(1).

Common Pitfalls

- Forgetting the odd-case bye team (+1 in next round).
- Mixing current-round team count with next-round team count.
- Overcomplicating proof: one match always removes one team.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int numberOfMatches(int n) {
        int matches = 0;
        while (n > 1) {
            if ((n & 1) == 0) {
                matches += n / 2;
                n /= 2;
            } else {
                matches += (n - 1) / 2;
                n = (n - 1) / 2 + 1;
            }
        }
        return matches;
    }
}
func numberOfMatches(n int) int {
    matches := 0
    for n > 1 {
        if n%2 == 0 {
            matches += n / 2
            n /= 2
        } else {
            matches += (n - 1) / 2
            n = (n-1)/2 + 1
        }
    }
    return matches
}
class Solution {
public:
    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;
    }
};
class Solution:
    def numberOfMatches(self, n: int) -> 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
var numberOfMatches = function(n) {
  let matches = 0;
  while (n > 1) {
    if (n % 2 === 0) {
      matches += n / 2;
      n = n / 2;
    } else {
      matches += (n - 1) / 2;
      n = (n - 1) / 2 + 1;
    }
  }
  return matches;
};

中文

题目概述

有 n 支队伍参加淘汰赛。每轮两两配对；若队伍数为奇数，会有一支队伍轮空直接晋级。请返回直到产生冠军为止的总比赛场次。

核心思路

每场比赛都会淘汰恰好一支队伍。总队伍从 n 变成 1，说明总共淘汰了 n-1 支队伍，因此总比赛数必然是 n-1。也可以按题意逐轮模拟，结果一致。

算法步骤

- 令 matches = 0。
- 当 n > 1 时循环：
  • 若 n 为偶数：本轮 n/2 场，下一轮队伍为 n/2。
  • 若 n 为奇数：本轮 (n-1)/2 场，下一轮队伍为 (n-1)/2 + 1（含轮空队）。
- 最后返回 matches。

复杂度分析

按轮模拟：时间复杂度 O(log n)，空间复杂度 O(1)。
若直接用结论 n-1：时间 O(1)，空间 O(1)。

常见陷阱

- 奇数轮没有把轮空队伍加回下一轮。
- 当前轮和下一轮人数更新混淆。
- 忽略“每场淘汰 1 队”这个关键不变量。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int numberOfMatches(int n) {
        int matches = 0;
        while (n > 1) {
            if ((n & 1) == 0) {
                matches += n / 2;
                n /= 2;
            } else {
                matches += (n - 1) / 2;
                n = (n - 1) / 2 + 1;
            }
        }
        return matches;
    }
}
func numberOfMatches(n int) int {
    matches := 0
    for n > 1 {
        if n%2 == 0 {
            matches += n / 2
            n /= 2
        } else {
            matches += (n - 1) / 2
            n = (n-1)/2 + 1
        }
    }
    return matches
}
class Solution {
public:
    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;
    }
};
class Solution:
    def numberOfMatches(self, n: int) -> 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
var numberOfMatches = function(n) {
  let matches = 0;
  while (n > 1) {
    if (n % 2 === 0) {
      matches += n / 2;
      n = n / 2;
    } else {
      matches += (n - 1) / 2;
      n = (n - 1) / 2 + 1;
    }
  }
  return matches;
};

Comments