Count of Matches in Tournament

Easy
0/40
Average time to solve is 20m
profile
Contributed by
8 upvotes
Asked in company
Barclays

Problem statement

You are given a positive integer 'N' representing the number of teams playing in a tournament. Your task is to find the total number of matches played in the tournament if the condition for the tournament is as follows:

1. If the current number of teams(N) playing in the tournament is even then, a total of N / 2 matches will be played. The winning N / 2 teams will advance to the next round, and the losing N / 2 teams will be eliminated.

2. If the current number of teams(N) playing in the tournament is odd then, 1 team will be advanced to the next round directly, and a total of (N - 1) / 2 matches will be played. The winning (N - 1) / 2 teams will advance to the next round, and the losing (N - 1) / 2 teams will be eliminated.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer, ‘T,’ which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first and the only line of each test case contains one integer 'N', as described in the problem statement.
Output Format: 
For each test case, print a single line containing a single integer denoting the total number of matches played in the tournament.

The output of each test case will be printed in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N <= 10 ^ 8

Time Limit: 1 second
Sample Input 1:
1
9
Sample Output 1:
8
Explanation for sample input 1:
In the first round, 8 teams will play 4 matches, and 1 team will be directly advanced to the next round. So including the winners of the first round, a total of 5 teams will advance to the next round.

In the second round, 5 teams will play 2 matches, and 1 team will directly advance to the next round. So including the winners of the second round, a total of 3 teams will advance to the next round.   

In the third round, 3 teams will play 1 match, and 1 team will directly advance to the next round. So including the winners of the third round, a total of 2 teams will advance to the next round.

In the final round, the 2 teams will play 1 match, and then there will be a winner of the tournament.

Therefore the total number of matches played is 4 + 2 + 1 + 1 = 8.
Sample Input 2:
2
32
78
Sample Output 2:
31
77
Hint

Simply count the total number of matches by implementing the given condition.

Approaches (2)
Recursive Method

In this approach, we will be calculating the answer by recursion. We know that if the current number of teams(N) is even, then they will be playing N / 2 matches in this round, and the remaining N / 2 teams will play till there is a final winner. If the current number of teams is odd, then they will play (N - 1) / 2 matches, and the remaining (N - 1) / 2 + 1 teams will advance to the next round and play till there is a final winner. So we can simply write a recursive relation for the number of matches.

The recursive relation is as follows:

  • totalMatches(N) = Matches played in this round + totalMatches(remaining teams).

 

Steps:

 

  • Create a function named totalMatches(N) that will calculate the total number of matches played in the tournament.
  • totalMatches(N):
    • If N == 1:
      • return 0.
    • Create a variable to store the answer (say, ans) and initialize it to 0, i.e., ans = 0.
    • If N is odd:
      • ans = (N - 1) / 2 + totalMatches((N - 1) / 2 + 1).
    • else:
      • ans = N / 2 + totalMatches(N / 2).
    • Finally, return the ans variable.
Time Complexity

O(log(N)), where N is the total number of teams.

 

Since in each round, half of the teams are getting eliminated, therefore a total of log(N) rounds will be played. Hence, the time complexity will be O(log(N)).

Space Complexity

O(log(N)), where N is the total number of teams.

 

Since a recursion stack will be created log(N) space will be required for it.

Code Solution
(100% EXP penalty)
Count of Matches in Tournament
Full screen
Console