Count of Matches in Tournament

easy math simulation tournament

Problem

A tournament starts with n teams. Each round, if the team count is even they all pair up: n / 2 matches are played and n / 2 teams advance. If the count is odd, one team advances for free and the rest pair up: (n − 1) / 2 matches are played and (n − 1) / 2 + 1 teams advance. Return the total number of matches played until a single winner remains.

Inputn = 7

Output6

7 → 3 matches, 4 advance; 4 → 2 matches, 2 advance; 2 → 1 match, 1 winner. Total = 3 + 2 + 1 = 6.

n (number of teams)

def numberOfMatches(n):
    matches = 0
    while n > 1:
        if n % 2 == 0:
            matches += n // 2       # all teams pair up
            n //= 2                 # n/2 teams advance
        else:
            matches += (n - 1) // 2  # one team skips, rest pair
            n = (n - 1) // 2 + 1     # winners + the lucky skipper
    return matches

function numberOfMatches(n) {
  let matches = 0;
  while (n > 1) {
    if (n % 2 === 0) {
      matches += n / 2;              // all teams pair up
      n = n / 2;                     // n/2 teams advance
    } else {
      matches += (n - 1) / 2;        // one team skips, rest pair
      n = (n - 1) / 2 + 1;           // winners + the lucky skipper
    }
  }
  return matches;
}

int numberOfMatches(int n) {
    int matches = 0;
    while (n > 1) {
        if (n % 2 == 0) {
            matches += n / 2;            // all teams pair up
            n = n / 2;                   // n/2 teams advance
        } else {
            matches += (n - 1) / 2;      // one team skips, rest pair
            n = (n - 1) / 2 + 1;         // winners + the lucky skipper
        }
    }
    return matches;
}

int numberOfMatches(int n) {
    int matches = 0;
    while (n > 1) {
        if (n % 2 == 0) {
            matches += n / 2;            // all teams pair up
            n = n / 2;                   // n/2 teams advance
        } else {
            matches += (n - 1) / 2;      // one team skips, rest pair
            n = (n - 1) / 2 + 1;         // winners + the lucky skipper
        }
    }
    return matches;
}

Explanation

The straightforward approach is direct simulation: replay the tournament one round at a time. We keep a running matches total and shrink n until only the champion is left.

When n is even, every team finds a partner, so n / 2 matches are played and exactly n / 2 teams survive. When n is odd, one team gets a bye (advances without playing) and the remaining n − 1 teams form (n − 1) / 2 pairs; the survivors plus the bye team give (n − 1) / 2 + 1 teams for the next round.

The loop stops once n reaches 1, at which point matches holds the answer. For n = 7 the rounds produce 3, 2, and 1 matches, totalling 6.

There is a beautiful O(1) shortcut: every single match eliminates exactly one team, and we must eliminate all but the winner. So the answer is always n − 1, no matter how the byes fall. The simulation above is kept because it visibly demonstrates why that identity holds round by round.

Time: O(log n) Space: O(1)