2nd smallest number puzzle
There is 38 numbers. What is the least number of comparison needed to find the 2nd smallest out of them?
Expert Asked on 11th December 2017 in Hadest puzzles.
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.
More puzzles to try-
Find the faulty machineA factory manufacturing flywheels for racing cars has ten machines to make them. The manufacturer knows the correct weight for ...Read More »
Akbar BirbalTo tease, King Akbar told his most clever advisor Birbal to give his daughter one thing that she can eat ...Read More »
Irene killed PeopleIrene 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 batteriesYou have a flashlight that takes 2 working batteries. You have 8 batteries but only 4 of them work. What ...Read More »
Petrol leakage riddleI traveled from London to Glasgow last week at 60 miles per hour, I had filled my petrol tank just ...Read More »
Fill the heartIt can fill a room or just one heart. Others can have it, but it can not be shared. What ...Read More »
Substraction brain teaserHow many times can 10 be subtracted from 100?Read More »
Boating in the RiverYou 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 puzzleYou 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 matrixIn this ball puzzle, complete the series by finding the value of ?(Question mark)Read More »
Number of days workedA man persuaded Weary Willie, with some difficulty, to try to work on a job for thirty days at eight ...Read More »
Square PuzzleCount number of squares in picture below ?Read More »
1996 riddleUse 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 puzzleThere are 10 stacks of 10 coins each. Each coin weights 10 gms. However, one stack of coins is defective ...Read More »
5 Little creatures riddleWe are very little creatures. All of us have different features. One of us in glass is set; one of ...Read More »
Milk Jugs PuzzleA 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 riddleWhere does Santa and his reindeer go to get hot chocolate while flying in the sky?Read More »
Couple betrayal puzzleA 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