# 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?

SherlockHolmes Expert Asked on 11th December 2017 in

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.

• ## 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 »