Click here to read the complete problem statement.
I need some clues for this problem
To find the two heaviest boxes among 256 boxes using comparisons, we can pair them and find the heaviest in 255 tries, and second heaviest one is the one that lost in the 7th round
Isn’t the answer 254?
I won’t spoil the answer here, but this is how to get the answer:
imagine a knockout style tournament. The heavier box moves on to the next round and the less heavier one is disqualified.
If we construct a tree like structure with the comparisons, we can get the heaviest box with 256-1 = 255 comparisons
Now, all the boxes that lost to the heaviest one could be the 2nd highest.
The comparison tree is a binary tree, calculate its diameter.
Diameter means the depth of the tree, look it up if you need help
We need at least (diameter - 1 + 255) comparisons to find the 2 heaviest boxes
Calculate this number yourself