# Overthought non-recursive 3ms C++ solution

• The recursive or tail-recursive solutions, building up the pairs, are more elegant than mine.

I thought about the patter, and built up the orders of the teams in a linked list starting with just 1 team; then wrote it out to a string with a formula for the correct number of parentheses.
Every time we double the number of teams to a new binary order of magnitude, we leave the teams that were there in place, and match each with one from the upper half in reverse order (1 to the highest, 2 [wherever it is] to the 2nd highest, etc.) so the sum of each pair in the first-round matches is the same, 1 more than the number of teams.
Starting with 2 teams, 1 plays 2. Double to 4 teams, 1 plays 4 [sum is 5], and 2 plays 3 [sum is 5], then match the winner of the (1,4) to the winner of (2,3).

For 8, the pairs are (1,8),(2,7),(3,6),(4,5) but in order that's 1,8,4,5,2,7,3,6.

The number of parentheses is the log-base-2 of the greatest-power-of-2-divisor of the position in the list.

I don't know if that English is easier to follow than the code.

I would have liked to find a formula to drop the teams into their slots (and the number of parentheses after them in a parallel array) without a linked list, but I couldn't find it.

``````class Solution {
protected:
static const int contestmax = 12; // This is a given in the statement of the problem
// 1-based Array to hold the linked list, as cursors
// 0 is the sentinel
int linkedlist [ 1 << contestmax + 1];

int what_pow_of_2(int n)
{
int greatest_pow_2_divisor = 1;
int logg = 0;
while (1)
{
if (n & greatest_pow_2_divisor)
return logg;
logg++;
greatest_pow_2_divisor <<= 1;
}
}

void insert(int val, int after)
{
}

public:

string findContestMatch(int n)
{

int maxavail = n;
int nextavail = 2;
int seeded = 1;

while (seeded < n)
{
// Each time we double the number of teams to a new binary order of magnitude,
// add one of the new teams after each of the existing teams, highest after 1,
// next highest after 2, etc.

int pairtotal = seeded * 2 + 1;
int curr = 1;
while (curr != 0)
{
insert((pairtotal - curr), curr);
}
seeded <<= 1;
}

// Now the teams are in the right order
// Write them to the string with the correct number of parentheses,
// which is the log-base-2 of the greatest power of 2 that divides
// the 1-based position, which is zero for odd positions, close parentheses,
// then a comma, then the same number of open parentheses except
// no comma and no open parentheses at the end.

int curr = 1;
string out = "";
int pos = 1;
int maxlog = what_pow_of_2(n);
for (int i = 0; i < maxlog; i++)
out += "(";
while (curr != 0)
{
out += to_string(curr); // or use string streams, and itoa of your choice
int p = what_pow_of_2(pos);
for (int i = 0; i < p; i++)
out += ")";
if (pos < n)
{
out += ",";
for (int i = 0; i < p; i++)
out += "(";
}
pos++;
}
return out;
}
};
``````

In an attempt to be even faster I used this routine to pre-generate the strings for between 0 and 128 teams, and return those strings for the corresponding input, but it didn't save measurable time, probably because 256, 1024, 2048, and 4096 took most of the time, and I didn't feel like pasting those strings into the code.

Is there a conventional word for the the highest power of 2 that divides a number, which is the same as the number which is all the zero bits and the first one bit from the least significant? (And is there a better way to find it?)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.