2nd smallest number puzzle
909.1K 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-
Find the faulty machine
A factory manufacturing flywheels for racing cars has ten machines to make them. The manufacturer knows the correct weight for ...Read More »Akbar Birbal
To tease, King Akbar told his most clever advisor Birbal to give his daughter one thing that she can eat ...Read More »Irene killed People
Irene killed hundreds of people mercilessly and yet the police were not able to put her behind the bars. Why?Read More »You have a flashlight and 8 batteries
You have a flashlight that takes 2 working batteries. You have 8 batteries but only 4 of them work. What ...Read More »Petrol leakage riddle
I traveled from London to Glasgow last week at 60 miles per hour, I had filled my petrol tank just ...Read More »Fill the heart
It can fill a room or just one heart. Others can have it, but it can not be shared. What ...Read More »Substraction brain teaser
How many times can 10 be subtracted from 100?Read More »Boating in the River
You are on a Boat in the mid of a river. You have two cigarettes with you. One of these ...Read More »Which man gets the cow?
Two men come before the king because one of their beloved pets has been claimed by the other. Both of ...Read More »Measuring water puzzle
You had an infinite supply of water and a 5 ml and 3 ml gallons. How would you measure exactly ...Read More »Missing value in ball matrix
In this ball puzzle, complete the series by finding the value of ?(Question mark)Read More »Number of days worked
A man persuaded Weary Willie, with some difficulty, to try to work on a job for thirty days at eight ...Read More »Square Puzzle
Count number of squares in picture below ?Read More »1996 riddle
Use the numerals 1, 9, 9 and 6 exactly in that order to make the following numbers: 28, 32, 35, ...Read More »Defective stack of coins puzzle
There are 10 stacks of 10 coins each. Each coin weights 10 gms. However, one stack of coins is defective ...Read More »5 Little creatures riddle
We are very little creatures. All of us have different features. One of us in glass is set; one of ...Read More »Milk Jugs Puzzle
A milkman has two empty jugs: a three gallon jug and a five gallon jug. How can he measure exactly ...Read More »Which one is telling the truth?
Mrs. Stotch is a fifth grade teacher. One of her students took her apple. Mrs. Stotch has narrowed the suspects ...Read More »Santa Hot Chocolate store funny riddle
Where does Santa and his reindeer go to get hot chocolate while flying in the sky?Read More »Couple betrayal puzzle
A couple (say A and B) decided to commit suicide after a rough life. They decided to jump off 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