Output Contest Matches

MediumGreedyStack

Description

Given n teams numbered 1 to n, pair them for matches so stronger teams meet weaker first. Output the bracket format.

Examples

Input:n = 4
Output:"((1,4),(2,3))"
Explanation:

The bracket matching algorithm pairs the strongest team (rank 1) with the weakest (rank n), second strongest with second weakest, and so on. This greedy pairing is applied recursively: after forming n/2 pairs in round one, these pairs become the new 'teams' for the next round, creating nested parentheses until only one match remains.

Input:n = 2
Output:"(1,2)"
Explanation:

This is the smallest possible tournament with only 2 participants. They are directly paired against each other, so the bracket is simply (1,2).

Input:n = 16
Output:"((((1,16),(8,9)),((4,13),(5,12))),(((2,15),(7,10)),((3,14),(6,11))))"
Explanation:

With 16 participants, the tournament creates a more complex nested structure. The pairing follows the pattern where team 1 pairs with team n, team 2 with team n-1, and so on, then these pairs are recursively grouped into larger brackets.

Constraints

  • n is power of 2, 2 ≤ n ≤ 2¹²

Ready to solve this problem?

Practice solo and sharpen your skills for technical interviews.