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.
1#include <stdio.h>
2
3int numberOfMatches(int n) {
4 int matches = 0;
5 while (n > 1) {
6 if (n % 2 == 0) {
7 matches += n / 2;
8 n /= 2;
9 } else {
10 matches += (n - 1) / 2;
11 n = (n - 1) / 2 + 1;
12 }
13 }
14 return matches;
15}
16
17int main() {
18 int n = 7;
19 printf("%d\n", numberOfMatches(n)); // Output: 6
20 return 0;
21}The function numberOfMatches uses a loop to repeatedly determine the number of matches in each round and adjust the number of teams until a single team remains. If the number of teams n is even, n / 2 matches are played. If n is odd, (n - 1) / 2 matches occur, and one team directly advances.
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
int numberOfMatches(int n) {
return n - 1;
}
int main() {
int n = 7;
std::cout << numberOfMatches(n) << std::endl; // Output: 6
return 0;
}This solution in C++, like its C counterpart, uses a mathematical reasoning to compute the number of matches, knowing that each team except one must be eliminated.