Testbook Test Series [closed]

Question

Assume there are 1024 men,each with distinct arm strength,in an arm wrestling match stronger arm always wins.Number of arm wrestling matches required to find men with strongest and second strongest arm in worst case is ______.

I got right for the strongest one i.e. 512+256+128+64+32+16+8+4+2+1=1023

for the second strongest wont it be the one who fought with the strongest one in the last match? Answer says for second strongest it will be 9 matches more.

Comments

http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/.

This is the concept, what you are doing is also correct basically the second strongest is the one that is at the top of the other part in the tree (Other part i mean apart from the Winner side) or the one that lost in the battle with the strongest.Thus Total will always be:
(N-1) For Winner and logN-1 for second best.

---

Sir correct me if i am going wrong. Once we have found the winner then instead for tracing back from the bottom we can move just one step down from the top. It will decrease the number of matches.

---

Not necessarily @jaig .. Instead of finding strongest and second strongest .Think of 1024 numbers and we need to find first and second largest number..Now this second largest number and first largest number can meet earlier , not necessarily below root ..And as a result second largest will be defeated by first largest number..

Hence we need to check all the opponents of with whom the largest element has played with in each level starting from till the final one..The maximum of those with whom the first maximum has encountered will be the second maximum..

Hence number of comparisons  =   n + log₂n - 2  , where n is number of elements..

---

ok now i got it  thank you sir :)