Sponsored
Sponsored
This approach involves treating the tournament rounds as iterative events where in each round, the number of matches is calculated, and non-advanced teams are eliminated until one team remains. This approach iterates over the number of teams until a winner is decided by subtracting the number of matches played from the total count of teams.
Time Complexity: O(log n) since in each step the number of teams is halved.
Space Complexity: O(1) since we only use a constant amount of additional memory.
1using System;
2
3public class Tournament {
4 public static int NumberOfMatches(int n) {
5 int matches = 0;
6 while (n > 1) {
7 if (n % 2 == 0) {
8 matches += n / 2;
9 n /= 2;
10 } else {
11 matches += (n - 1) / 2;
12 n = (n - 1) / 2 + 1;
13 }
14 }
15 return matches;
16 }
17
18 public static void Main() {
19 int n = 7;
20 Console.WriteLine(NumberOfMatches(n)); // Output: 6
21 }
22}The C# solution keeps track of the matches and the evolving number of teams until only one team remains. This iterative approach optimizes the calculation of matches each round.
Instead of simulating each round, this approach uses the observation that to find a winner among n teams, exactly n - 1 matches must be played. This is because each match eliminates exactly one team and n - 1 eliminations leave one champion.
Time Complexity: O(1)
Space Complexity: O(1)
1
The function numberOfMatches directly returns n - 1 under the logical deduction that each match will remove one team until only one team remains.