8

you have 32 numbers. What is the least number of comparison needed to find the 2nd smallest out of them.

As per me it 61 comparsisons are required. Compare first two number in list. Assign largest and second largest to them based on comparison. Now compare rest 30 numbers with two of them and assign largest and second largest based on comparison. So for rest of 30 numbers we have to do 2 comparison for each number . this answer is 30*2 + 1 = 61. Can 61 be reduced?

user3198603
  • 183

3 Answers3

11

I happen to remember this one from my algorithms class. Take your list of 32 numbers and try to find the smallest number. Compare the first and second numbers, the third and fourth, etc. until you reduce the list by half and repeat. It will take 31 comparisons to find the smallest number as each comparison eliminates one possibility.

Once this has been complete, make a list of the numbers the smallest number has been compared to. There should be 5. It will take 4 comparisons to find the smallest of these 5 numbers, for a total of 35 comparisons.

Mike
  • 13,318
  • Near-simulpost! You were 10 seconds after me (by my clock) with the same algorithm and answer. :) – Charles Apr 27 '14 at 05:41
  • @Charles Yep, it happens. Did you really just upvote your own answer by the way? I saw it as posted 7 seconds ago and it already had an upvote. – Mike Apr 27 '14 at 05:42
  • Not me, must have been someone else. I'll give you +1, though -- I can't fault your answer, of course. – Charles Apr 27 '14 at 05:44
  • @Charles Strange. Ah well, +1 to yours as well. – Mike Apr 27 '14 at 05:55
  • @Mike one can't upvote one's post :-) by the way I think it will help if you explain why the smallest element will be compared only to $5$ other numbers. (I know it's $\log_2 32$ though :-P) – Ant Apr 27 '14 at 15:32
  • @ant Seems you're correct, just tested it. It was just hard to believe someone read and upvoted in 7 seconds. The other thing is just a minor detail. The list must be reduced by half 5 times to reduce the list from 32 to 1. – Mike Apr 27 '14 at 15:41
  • Ok, so we can do it in 35 using this particular method ... but how do you prove that there is not some other method that can do it in less than 35? – Bram28 Jun 05 '19 at 16:06
8

35 comparisons are optimal. Pair off the numbers and test them against each other. Take the winners, the winners' winners, and so forth to find the maximal element; this takes 31 comparisons in all. Now the maximal element was compared against five other elements, and the second-largest element is precisely the largest of these five. You can find it in four comparisons, for a total of 35 comparisons.

Charles
  • 32,122
0

The answer is 35

lets assign the sequence to each number, position 1 to position 32.

  • If numbers are sorted then 0 Comparisons

  • If numbers are unsorted

  • Pair the adjacent positions (1 ,2) (3,4) (5,6) ... (31, 32)

  • Iteration 1: Compare each group, find the smallest in each group. 16 Comparisons

Follow the same pairing logic

  • Iteration 2: 8 comparisons(Find the smallest)

  • Iteration 3: 4 comparisons(Find the smallest)

  • Iteration 4: 2 comparisons(Find the smallest)

  • Iteration 5: 1 Comparison (Find the smallest)

    So total required is 31 comparisons

Now traverse back to the tree , the ones who lost against the final smallest element.

We will have 5 such elements , If we need to find the second smallest, If we use a balance binary tree, there are at most 5 such values which require 4 comparisons.

Community
  • 1
Srikanth
  • 101