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.
1public class Tournament {
2 public static int numberOfMatches(int n) {
3 int matches = 0;
4 while (n > 1) {
5 if (n % 2 == 0) {
6 matches += n / 2;
7 n /= 2;
8 } else {
9 matches += (n - 1) / 2;
10 n = (n - 1) / 2 + 1;
11 }
12 }
13 return matches;
14 }
15
16 public static void main(String[] args) {
17 int n = 7;
18 System.out.println(numberOfMatches(n)); // Output: 6
19 }
20}The Java solution follows the same logical steps as the C/C++ solutions, iterating through the rounds of the tournament while counting and reducing the number of teams.
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.