2nd smallest number puzzle
963.2K Views
There is 38 numbers. What is the least number of comparison needed to find the 2nd smallest out of them?
Answer: 52 comparisons which is also the worst case
Here’s how the algorithm works:
- Divide the 38 numbers into pairs, and find the smallest number in each pair. This takes 19 comparisons.
- Take the 19 smallest numbers and pair them up again, finding the smallest number in each pair. This takes 18 comparisons.
- Take the 9 smallest numbers and pair them up again, finding the smallest number in each pair. This takes 8 comparisons.
- Take the 5 smallest numbers and pair them up again, finding the smallest number in each pair. This takes 4 comparisons.
- Take the 3 smallest numbers and pair them up again, finding the smallest number in each pair. This takes 2 comparisons.
- 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.
Your Answer
More puzzles to try-
Whats going on riddle
A man leaves home, turns left, goes straight, turns left again, goes straight and turns left once more then returns ...Read More »Tuesday, Thursday what are other two days staring with T?
Four days are there which start with the letter ‘T‘. I can remember only two of them as “Tuesday , Thursday”. ...Read More »How will the logicians manage ?
A convention is held where all the big logicians are summoned. The master places a band on everyone’s forehead. Now ...Read More »Wire Cube riddle
Say you have some bendable wires (any number, any length). What is the minimum number of solder connections needed to ...Read More »Ninety One Riddle
Below equation is true. 8 + 8 = 91 How ?Read More »Box in the Carton
John can place six large boxes or nine small boxes into a carton. Can you find out in how many ...Read More »Mechanical Computer riddle
The Puzzlefry mechanical computer is a very sensitive device, it consists of interlocked toothed gear cogs. The largest Cog has ...Read More »Transport Puzzle
A man transports a fox, a duck and corn in a boat. The boat is only capable of transporting himself ...Read More »Stone and Eatable
Tell me the Hindi name of a Vegetable which if we remove 1st word will become a precious Stone and ...Read More »China and Japan
Why do Chinese men eat more rice than Japanese men do ?Read More »Wind Blows South and then North
Do you know of a place where the wind blows south and then suddenly shifts direction towards the north?Read More »Cards Probability Puzzle
Andrew is shuffling a pack of 54 cards in total and after some time, he takes out a joker card. ...Read More »What is it that no man wants
What is it that no man wants, but no man wants to lose?Read More »Time Measurement
How will you measure 15 minutes using two hourglasses of 7 minutes and 11 minutes respectively?Read More »Find hidden words Resturant picture puzzle
Find 6 hidden words in this ResturantRead More »What do you see in the given picture?
What do you see in the given picture?Read More »Table to eat
What kind of table is good for you to eat?Read More »Sequence Puzzle
There is this one man who killed his mother, was born before his father and married over 100 women without ...Read More »Tool of War
Helps to conquer, helps to protect. Sometimes threaten, sometimes defeat. Sometimes grows, sometimes shrinks. Results our downfall, results our success. ...Read More »How will you do that?
You are standing next to three switches. You know these switches belong to three bulbs in a room behind a ...Read More »
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