Knockout Bracket Check
You run the sign-up desk for a table tennis club's knockout tournament. In each round, players pair off and the losers go home, so the field halves every round. That only works cleanly if the number of players is 1, 2, 4, 8, 16, and so on. Any other count means someone gets a free pass (a "bye") in some round, and the players hate byes.
The sign-up screen takes whatever number the organiser types, including mistakes like 0 or -4. Before printing a bracket, the screen should say whether the count gives a bracket with no byes at all.
Your task
Write isFullBracket(players). Return true if players is a power of two (1, 2, 4, 8, …), and false otherwise.
0 and every negative number return false. 1 returns true: one player is champion without playing. Try to answer without a loop.
isFullBracket(players: int) → bool
Examples
players = 16
true
16 → 8 → 4 → 2 → 1. Every round halves the field evenly, so no byes. In binary, 16 is 10000: a single 1 bit.
players = 12
false
12 → 6 → 3, and 3 players cannot pair off. 12 is even, but being even is not enough. In binary, 12 is 1100: two 1 bits.
players = 1
true
1 is 2 to the power 0. In binary it is just 1, a single 1 bit.
Constraints
- -2,147,483,648 ≤ players ≤ 2,147,483,647
Start with brute force
Keep halving: while the number is even, divide it by 2. If you end at exactly 1, it was a power of two. This takes at most about 31 steps, so speed is not really the problem.
The trouble is the edges. With 0, "while even, halve" loops forever, because 0 / 2 is still 0 and still even. Negative numbers need their own care too. The bit trick answers in one step and the only edge to remember is n > 0.
Hints
0 of 4 shown- Hint 1
Write 4, 8 and 16 in binary, then 6, 12 and 20. What do the first three have in common that the others do not?
- Hint 2
A power of two has exactly one 1 bit. So the question becomes: does
playershave exactly one bit set? - Hint 3
Write 8 and 7 in binary, one above the other: 1000 and 0111. Now do the same for 12 and 11: 1100 and 1011. What does subtracting 1 do to the lowest 1 bit and the zeros below it? What does
n & (n - 1)give in each case? - Hint 4
n & (n - 1)erases the lowest 1 bit ofn. If that leaves 0, there was only one 1 bit. Checkn > 0first, because 0 and negative numbers are never powers of two and can fool the bit test.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
In binary, a power of two is a single 1 followed by zeros: 1, 10, 100, 1000. So you only need to check that a positive number has exactly one 1 bit.
Subtracting 1 turns the lowest 1 bit into 0 and every 0 below it into 1. Everything above stays the same. So n & (n - 1) is n with its lowest 1 bit removed.
n = 16is10000.n - 1 = 15is01111. AND gives00000. Nothing was left after removing one bit, so 16 is a power of two.n = 12is1100.n - 1 = 11is1011. AND gives1000, which is 8, not 0. A second bit survived, so 12 is not.n = 0:0 & -1is 0, which would wrongly say yes. That is why then > 0check comes first.
function isFullBracket(players) {
// A power of two has exactly one 1 bit.
// players & (players - 1) clears the lowest 1 bit.
return players > 0 && (players & (players - 1)) === 0;
}def is_full_bracket(players):
# A power of two has exactly one 1 bit.
# players & (players - 1) clears the lowest 1 bit.
return players > 0 and (players & (players - 1)) == 0Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.