2nd smallest number puzzle
1,056.6K 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-
Which are the requested two numbers. ?
Using the digits 1 up to 9, two numbers must be made. The product of these two numbers should be ...Read More »The Leaning Tower
It is said that Galileo (1564-1642) dropped balls of various weights from the top of the Leaning Tower of Pisa ...Read More »Jelly Give and Take puzzle
A boy and a girl each have a bag of containing the same number of jelly beans. How many jelly ...Read More »What was the third child’s name?
Johnny’s mother had three children. The first child was named April. The second child was named May. What was the ...Read More »Little Tommy
Little Tommy Tittle tat took two Ts, to tie two ups to two tall trees, to torment the terrible tittle ...Read More »How did he do it?
John put a coin in a bottle and put a cork on the bottle and later managed to get the ...Read More »How can we do it?
We all know that a chess board has 64 squares This can be completely covered by 32 cardboard rectangles, each ...Read More »Europe is like a frying pan
Why is Europe like a frying pan?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 »How much of a loss did the shopkeeper take?
A lady buys goods worth Rs 200 from a shop, whose shopkeeper is selling the goods with zero profit. The ...Read More »Mailman
Two friends, Denis and Léo wish to communicate by mail. The mailman is dishonest. He steals. Each of the two ...Read More »How can one live 10 days without sleeping?
How can one go 10 days without sleeping?Read More »Bacteria in a jar
The number of bacteria in a large sealed jar doubles every minute. The bacteria will take an hour to fill ...Read More »Help Andrew to solve the Rebus riddle
Andrew informed something to me, Instead of replying I gave me a paper having this rebus. Can you help Adrew ...Read More »Complex thing
What is the most complex thing man has yet we use it everyday?Read More »Multiplication puzzle
Multiple by 8 without using multiplication or addition Now do the same with 7?Read More »How do all three cross the river?
John, his wife and their daughter wish to cross a river. The row boat can only hold 100 kilos. John ...Read More »Children do not know
Children do not know it. Older men take care of it. Women are panicking because of it. Men take up ...Read More »Child of the water, but What am I?
I am the child of the water, yet when I return to the water, I die. What am I?Read More »Head Tail Puzzle
As it often happens in life evil warlock imprisoned a wise man. Surprisingly he gave him a chance to save ...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