Home

2nd smallest number puzzle

1,205.9K Views

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

Share
SherlockHolmes Expert Asked on 11th December 2017 in Hadest puzzles.
Add Comment
Cancel

    • 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.

    Cancel
    Moshe Expert Answered on 27th February 2023.
    Add Comment
    Cancel

    • Your Answer

    By posting your answer, you agree to the privacy policy and terms of service.

  • More puzzles to try-

  • Accenture Interview PuzzlesAdobe Interview PuzzlesAge RiddleAkbar Birbal PuzzlesAlgorithm PuzzlesAlphabet riddleAmazon Interview PuzzlesAnalytical MathematicsAptitude PuzzleBank PuzzlesBetting PuzzlesBrain TeasersCalendar PuzzlesCards PuzzlesChess Board PuzzleChess PuzzlesChristmas Puzzlecipher PuzzleCivil Services PuzzleClock time puzzleCognizant Interview PuzzlesCoins PuzzleComputational PuzzleconundrumCoronavirus PuzzleCoupondunia Interview PuzzleCritical Thinking Puzzledata analyticsData Structure Interview QuestionsDecode PuzzleDetective PuzzlesDice PuzzleDictionary Riddlesdifficult riddleEasy Math puzzlesEasy puzzlesEinstein puzzleEnglish RiddleFamily Tree Puzzlefamous puzzleFill in the blanks riddlesFinding Killer RiddlesFlipkart interview puzzlesFunny RiddlesGeneral KnowledgeGeographical PuzzleGoogle Code Jam 2014Google Interview PuzzlesGRE PuzzleHard Puzzle