algoadvance

You are given a positive integer n which denotes the number of teams in a competition. Each team is given a unique number from 1 to n. In each round, two teams compete against each other, and the winning team moves to the next round. There are n-1 rounds in total. After the final round, there is one winning team—the champion.

You need to find and return the number of the champion team using the following rule:

1. Teams with the same parity (odd/even) compete against each other.
2. After each round, the winner moves to the next round with the same number.

Example:

• Input: n = 4
• Output: 4

Clarifying Questions

1. How are the winners determined if teams have the same parity?
   • It was mentioned that the winner retains the same number, so the specific detailed rules of how each match winner is determined aren’t necessary since the problem guarantees that there’s only one champion.
2. Is n always an even number?
   • Yes, according to the problem statement, n will be an even number as each team with the same parity will have a matching opponent.

Strategy

The problem essentially boils down to progressively reducing the number of teams by half in each round, and then moving the winners to the next round until one team (the champion) remains. An efficient way to simulate this process without keeping track of the individual matchups is to keep reducing the number of teams by half until we are left with one team.

Steps

1. Start with the initial number of teams (n).
2. In each round, half of the teams move to the next round.
3. Continue this until we have only one team left.

Code

def findChampion(n: int) -> int:
    # The final winner after reducing the number of teams by half each round
    while n != 1:
        n = n // 2
    return n

# Example usage:
print(findChampion(4))  # Output: 1
print(findChampion(16))  # Output: 1

Time Complexity

• Time Complexity: O(log n)
  • In each round, we divide the number of teams by 2, which corresponds to a logarithmic reduction in the number of total teams.
• Space Complexity: O(1)
  • This solution uses a constant amount of space regardless of the input size n.

This provides an efficient way to determine the champion team number without explicitly simulating every single match.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?