Find the smallest and second smallest number in an array of 8 numbers with only 9 comparisons

Question

This is an interview question I had to answer. Well a friends actually but he asked me and I didnt know the answer also. Hence I'm asking here:

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

I'm note sure how you can do it using only 9 comparisons. This is how close I have come to it. (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 a function isLessThan() to keep track of the number of comparisons. Again, this does 10 comparisons. How is it possible to do it in 9 comparisons. Or in n+log(n)-2 time?

P.S: I implemented it in java but it can be any language

Answer 1

A way to think about the solution is this is like a tennis knock-off competition series. Suppose each number corresponds to a player. Pair off the numbers and let each game correspond to a comparison between 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 will have been defeated only by the winner. Suppose a3 is the winner. Then the second best will be a4, a12 or a5678.

Games: (a4, a12)

Winner: a412

Games: a(412, 5678)

Winner: a4125678

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

Hence number of games = 7 + 2 = 9 = (n + lg(n) - 2)

This is easier to visualize the above competition a tree:

               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 ultimate winner a3 will have traversed a path from the leaf to the root (lg(n) -1). In his path, he will have defeated the second-best player, which is one of {a4, a12, a5678}. So we can just figure out who is the second best by looking at the max in the path apart from the winner which is as described.

Answer 2

As a hint, set up an elimination tournament bracket for the elements of the array to play in. The biggest number in the array will win the tournament, and you'll only need n - 1 comparisons if n is a power of two.

The second-largest element must have lost only to the largest, and in the tournament the largest element only beat log n other elements. Play a second elimination tournament of just those elements to find the largest element there, which requires log n - 1 comparisons.

Overall, only n + log n - 2 total comparisons are needed. All that's left is to code it up.

Hope this helps!