You are given an integer n, the number of teams in a tournament that has strange rules:

• If the current number of teams is even, each team gets paired with another team. A total of n / 2 matches are played, and n / 2 teams advance to the next round.
• If the current number of teams is odd, one team randomly advances in the tournament, and the rest gets paired. A total of (n - 1) / 2 matches are played, and (n - 1) / 2 + 1 teams advance to the next round.

Return the number of matches played in the tournament until a winner is decided.

Constraints:

• 1 <= n <= 200

Approach: Simulation

Intuition

The problem simulates a knockout tournament where, in each round, teams are paired to play matches. Every match eliminates one team. If there's an odd number of teams, one team gets a bye (automatically advances). This process continues until only one team remains.

Algorithm

1. Initialize:
   Set a counter ans to track the total number of matches played.

2. Iterate Through Rounds:

   • While more than one team remains (n > 1):
     • Calculate the number of matches in the current round as n / 2 and add it to ans.
     • Update the number of teams for the next round:
       • If n is even, all teams are paired, so next round has n / 2 teams.
       • If n is odd, one team gets a bye, so next round has n / 2 + 1 teams.

3. Return the Result:
   Once the loop finishes, ans contains the total number of matches played.

Complexity Analysis

• Time Complexity:
  O(log n)
  Each round roughly halves the number of teams, leading to a logarithmic number of iterations.

• Space Complexity:
  O(1)
  The algorithm uses only a constant amount of extra space.

Wrap up

If you found this guide helpful, consider subscribing to my newsletter on jyotirmoy.dev/blogs , You can also follow me on Twitter jyotirmoydotdev for updates and more content.