Find the smallest and second smallest number in an array of 8 numbers, total 9 comparisons

Question

This is an interview question that I had to answer. Well, friends really, but he asked me, and I also did not know the answer. So I ask here:

Given an array of 8 integers, find the smallest and second smallest integer using only 9 comparisons. More specifically, in n+log(n)-2 times.

I am sure you can do this using only 9 comparisons. That's how close I came to him. (10 comparisons)

 public class Comp { static int[] nums = new int[]{9, 4, 5, 3, 2, 7, 6, 1}; static int compcount = 0; //int[] is nums[] array public static int[] twoLeast(int[] a){ int min1 = a[0]; //Prospective lowest number int min2 = a[1]; //Prospective second lowest number if(isLessThan(min2, min1)){ min1 = a[1]; min2 = a[0]; } for(int i=2; i<a.length;i++){ if(isLessThan(a[i], min1)){ min2 = min1; min1 = a[i]; }else if(isLessThan(a[i], min2)){ min2 = a[i]; } } return new int[]{min1, min2}; } public static boolean isLessThan(int num1, int num2){ compcount++; return num1 < num2; } } 

Here I have the isLessThan() function to track the number of comparisons. Again, this makes 10 comparisons. How can this be done in 9 comparisons. Or in n+log(n)-2 time?

PS: I implemented it in java, but it can be any language

Answer 1

The way to think about a solution is like a series of tennis tearing competitions. Suppose each number corresponds to a player. Combine the numbers and let each game correspond to a comparison of numbers within a pair:

Games: (a1,a2) , (a3, a4) , (a5, a6) , (a7, a8)

Winners: a12 , a34 , a56 , a78

Games: (a12, a34) , (a56, a78)

Winners: a1234 , a5678

Game: (a1234, a5678)

Winner: a12345678

Number of games = 7 ==> (n - 1)

The second best result will be defeated only by the winner. Suppose a3 is the winner. Then the second best would be a4 , a12 or a5678 .

Games: (a4, a12)

Winner: a412

Games: a(412, 5678)

Winner: a4125678

So, we have games 2 for the second best ==> (lg(n) - 1)

Therefore, the number of games = 7 + 2 = 9 = (n + lg(n) - 2)

It is easier to visualize the above tree competition:

  a12345678 / \ / \ / \ / \ a1234 a5678 / \ / \ / \ / \ a12 a34 a56 a78 / \ / \ / \ / \ a1 a2 a3 a4 a5 a6 a7 a8 

If a3 is the winner, we have:

  a3 | /----|----\ / \ / \ / \ a3 >==========> a5678 / \ / \ / \ / \ a12 <====< a3 a56 a78 / \ / \ / \ / \ a1 a2 a3 ->a4 a5 a6 a7 a8 

Basically, the final winner a3 will go from leaf to root ( lg(n) -1 ). On his way, he will defeat the second best player, who is one of {a4, a12, a5678} . Thus, we can simply find out who is second, looking at the maximum on the path, except for the winner, who is described as described.

Answer 2

As a hint, adjust the tournament tournament bracket for array elements. The largest number in the array will win the tournament, and you will need only n - 1 comparisons, if n is a force of two.

The second largest element was to be lost only to the largest, and in the tournament the largest element only beat log n other elements. Lose the second tournament to destroy only those elements to find the largest element there that requires log n - 1 comparisons.

In general, only n + log n - 2 general comparisons are required. It remains only to encode it.

Hope this helps!