How to find the third largest number out of 4 inputs without using arrays and only using three comparators or comparisons

Question

The code that I have written is as follows :

 /*
    Program to find the 3rd largest no from 4 nos without using arrays and
 only using 3 comparators or comparisons

     */
    package d;


    public class thirdlargest {
        public static void main(String args[]) {

           int a=1,b=2,c=3,d=4,soln;
           soln= Math.min(Math.max(a,b),Math.max(c,d));
           System.out.println("Third largest=" +soln);        
        }
    }
    /*
    Output:
    Third largest=2
     */

But this only works for the used pattern of input if I change the pattern the output will be wrong. How can I fix this code with only using 3 comparators or comparisons strictly and we can use any programming language

Answer 1

IMO it is not possible to find third largest number out of 4 numbers using only three comparisons:

 public static void main(String[] args) throws IOException {
        int a=1,b=2,c=3,d=4,soln;
        int maximum1 = Math.max(a,b);
        int maximum2 = Math.max(c,d);

        if(maximum1 < maximum2) {
            // either c or d and we need more comparisons
        }
        else {
            // either a or b and we need more comparisons
        }
    }

Edit: Actually we can find the largest number or smallest number using 3 comparisons but probably not the third largest etc.

Also check this answer for finding kth largest number in O(n) time.

Answer 2

This answer on the Math StackExchange site discusses the problem of finding the 2nd largest of N values. It states (with proof) that the lower (tight) bound is N + ceiling(log₂N) - 2

For N == 4, that evaluates to 4.

(This applies here because the 3rd largest of 4 is also the 2nd smallest of 4.)

I don't think the proof excludes (hypothetical) solutions with less than 4 comparisons that rely on the N numbers being unique. But that was not part of the problem statement.

Answer 3

I'm not sure what the exact definition of "comparator" is, the way they're using it. But assuming that Math.min and Math.max don't count as comparators, here's a way to compute it using no comparisons or comparators:

public static int thirdLargest(int a, int b, int c, int d) {
    int min = Math.min(a, Math.min(b, Math.min(c,d)));
    int offset = min + 1 - Integer.MIN_VALUE;
    a -= offset;
    b -= offset;
    c -= offset;
    d -= offset;
    min = Math.min(a, Math.min(b, Math.min(c,d)));
    return min + offset;
}

Computing the third largest number is the same as computing the second smallest number. The trick in this code is that it computes the smallest number, then subtracts from each number the exact offset needed to make the smallest number wrap around and become Integer.MAX_VALUE, while not wrapping around for the other values. The smallest of the remaining numbers is now the second smallest of the original numbers, minus the offset, which we'll add back.

However, I'll concede that this only works if all four numbers are distinct--or, at least, if the lowest two numbers are distinct. It fails if you give it a=1, b=1, c=2, d=3--it outputs 2 instead of 1. At least this should get you points for your problem-solving skill, which is what I assume the question is intended to find out. It had better not be to find out how you would actually solve this in a production situation, because putting restrictions like this on production code (no arrays) would be lunacy.

EDIT:

Here's another solution. There's one comparison in the code, but it's in a method that's executed three times, so that should count as three comparisons.

public static int thirdLargest(int a, int b, int c, int d) {
    if (isThirdLargest(a, b, c, d)) {
        return a;
    }
    if (isThirdLargest(b, a, c, d)) {
        return b;
    }
    if (isThirdLargest(c, a, b, d)) {
        return c;
    }
    return d;
}

public static boolean isThirdLargest(int a, int b, int c, int d) {
    int z = 3 + ((b - a) >> 31) + ((c - a) >> 31) + ((d - a) >> 31);
    // z = number of other parameters that are >= a.  Note that all of the
    // shift operations will return either 0 or -1.
    int y = 3 + ((a - b) >> 31) + ((a - c) >> 31) + ((a - d) >> 31);
    // y = number of other parameters that are <= a
    int x = -y >>> 31;
    // x = 1 if there are any other parameters <= a, 0 if not.  Note that
    // x can be 0 only if z == 3.
    int w = z & (x << 1);
    // This will be 2 if a is the third largest.  If z == 2, then x == 1
    // and w will be 2.  If z == 3, and x == 1, that means that a is the
    // smallest but is equal to at least one of the other parameters;
    // therefore a is also the third largest.  But if x == 0, a is
    // strictly smaller than all other parameters and is therefore not the
    // third largest.
    return w == 2;
}

Note: This may suffer from overflow problems, if there are two numbers that differ by 2³¹ or greater. Converting all the parameters to long should avoid the problem (also all the 31's would be changed to 63), but I haven't tested it.

Answer 4

Thanks to @invisal for link to algorithm to find the maximum of two numbers without using comparison operator.

I flipped it to return minimum instead, then used as follows to find second lowest value, aka third highest:

private static int thirdHighest(int a, int b, int c, int d) {
    int lowest = min(min(a,b),min(c,d));
    if (a == lowest)
        return min(min(b,c),d);
    if (b == lowest)
        return min(min(a,c),d);
    if (c == lowest)
        return min(min(a,b),d);
    return min(min(a,b),c);
}
private static int min(int a, int b) {
    return b - (((a - b) >> 31) & 0x1) * (b - a);
}

Exactly 3 == comparisons.

Works for input numbers in any order and also works if duplicate numbers are given.

Note: If inputs are constrained to be distinct, then the answer by @ajb can truly do it without any comparisons, by using the min/max bit manipulation of the link provided by @invisal.

Answer 5

The solution posted by @Andreas is very clean and readable. There is another solution that is less clean and less efficient. The solution relies on catching errors when dividing by zero. We keep on adding 1 to each number and then use the following expression to see if an error occurred:

1 / (currentNumber - Integer.MAX_VALUE)

The second number that threw an error will be the third largest number out of the four. Even though the code has 4 comparison operators =. It will only run two of these statements: One for the first error, and one for the second error. For a total of two comparison statements. This method works for any set of input integers, both positive and negative.

public class thirdlargest 
{
    public static void main(String args[]) 
    {
        System.out.println("Third highest number: " + thirdHighest(1, 2, 3, 4));     
        System.out.println("Third highest number: " + thirdHighest(4, 3, 2, 1));  
        System.out.println("Third highest number: " + thirdHighest(-5, -4, -3, -2));  
        System.out.println("Third highest number: " + thirdHighest(0, 0, 0, 0));  
    }

    private static int thirdHighest(int a, int b, int c, int d)
    {
        int testa = a, testb = b, testc = c, testd = d;

        int divisionResult;
        int numberFound = 0;

        while(true)
        {             
            try
            {
                divisionResult = 1 / (testa++ - Integer.MAX_VALUE); 
            }
            catch(Exception ex)
            {
                numberFound++;
                if(numberFound == 2)
                {
                    return a;
                }
            }

            try
            {
                divisionResult = 1 / (testb++ - Integer.MAX_VALUE); 
            }
            catch(Exception ex)
            {
                numberFound++;
                if(numberFound == 2)
                {     return b;
                }
            }

            try
            {
                divisionResult = 1 / (testc++ - Integer.MAX_VALUE); 
            }
            catch(Exception ex)
            {
                numberFound++;
                if(numberFound == 2)
                {
                    return c;
                }
            }

            try
            {
                divisionResult = 1 / (testd++ - Integer.MAX_VALUE); 
            }
            catch(Exception ex)
            {
                numberFound++;
                if(numberFound == 2)
                {
                    return d;
                }
            }
         }
    }
}

Answer 6

import java.util.Scanner;

public class TmaxFourNo {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter no.'s:");
        int w = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        int z = sc.nextInt();
        int m1 = Math.min(Math.max(w, x), Math.max(y, z));
        int m2 = Math.max(Math.min(w, x), Math.min(y, z));
        if (m1 < m2) {
            System.out.println("Tmax=" + m1);
        } else {
            System.out.println("Tmax=" + m2);
        }
        sc.close();

    }

}