2nd smallest number puzzle

1,043.9K Views

There is 38 numbers. What is the least number of comparison needed to find the 2nd smallest out of them?

Share
Add Comment

  • 1 Answer(s)

    Answer: 52 comparisons which is also the worst case

    Here’s how the algorithm works:

    1. Divide the 38 numbers into pairs, and find the smallest number in each pair. This takes 19 comparisons.
    2. Take the 19 smallest numbers and pair them up again, finding the smallest number in each pair. This takes 18 comparisons.
    3. Take the 9 smallest numbers and pair them up again, finding the smallest number in each pair. This takes 8 comparisons.
    4. Take the 5 smallest numbers and pair them up again, finding the smallest number in each pair. This takes 4 comparisons.
    5. Take the 3 smallest numbers and pair them up again, finding the smallest number in each pair. This takes 2 comparisons.
    6. Take the 2 remaining numbers and find the smallest one. This takes 1 comparison.

    Adding up the comparisons from each step gives us a total of 19+18+8+4+2+1=52 comparisons. However, in the worst case scenario, the two smallest numbers are always paired up in the last step.

    Moshe Expert Answered on 27th February 2023.
    Add Comment
  • Your Answer

    By posting your answer, you agree to the privacy policy and terms of service.
  • More puzzles to try-