## June 19, 2015

### Number Comparisons

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

Amlan Sahu said...

61

Amlan Sahu said...

61

Anonymous said...

62

Noggin Noddlebright said...

Sixty-One.
1. Compare the first two numbers in the sequence.
2. Compare the smaller of the two with the next number in the sequence.
3. Repeat until every number has been compared and the smallest is identified. (31 comparisons)
4. Repeat entire process excluding the smallest number already identified from the original set. (30 comparisons)

kpm said...

35.

First Round: Find the smallest number X - Do it like a tournament. 16 comparisons, then 8, then 4, then 2, finally a "winner". 16+8+4+2+1 = 31 to find the smallest number.

Second Round: Find the second smallest number Y- We know from the first round that the only number Y could have "lost" to was X. Take the 5 numbers that X was compared with and compare all of them. It will take 4 comparisons to find the smallest number out of these five numbers.

31+4 = 35.