# Count of Matches in Tournament

Posted: 11 Mar, 2021

Difficulty: Easy

#### 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.
```

##### 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
```

Approach 1

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.

- If

Approach 2

SIMILAR PROBLEMS

# Ceiling in a sorted array

Posted: 8 Jul, 2021

Difficulty: Moderate

# Game of 3

Posted: 11 Jul, 2021

Difficulty: Easy

# Postorder Traversal

Posted: 22 Jul, 2021

Difficulty: Easy

# Find All Subsets

Posted: 23 Jul, 2021

Difficulty: Easy

# Print All Subsets

Posted: 23 Jul, 2021

Difficulty: Easy