Given three numbers, find the second greatest of them

Question

I've just coded this for my country's programming Olympiad. I want to know if this method is a good approach in terms of readability and performance. I would also like to know how to improve it.

Note: We can assume all numbers entered are different, positive and smaller or equal to 100.

#include <stdio.h>                                                                                                                                                                                                                                                                                

int find_second(int a, int b, int c)                                                             
{                                                                                                                                                                                      
    if (a > b && b > c)                                                                             
    {                                                                                               
        return b;                                                                                   
    }                                                                                                                                                                                  
    else if (a > c && c > b)                                                                        
    {                                                                                               
        return c;                                                                                   
    }                                                                                                                                                                    
    else                                                                                            
    {                                                                                               
        return -1;                                                                                  
    }                                                                                               
}                                                                                                   

int main(void)                                                                                      
{                                                                                                                                             
    int a, b, c, second1, second2, second3;                                                               

    scanf("%d %d %d", &a, &b, &c);                                                                  

    second1 = find_second(a, b, c);                                                                
    second2 = find_second(b, c, a);                                                                
    second3 = find_second(c, a, b);

    if (second1 != -1)                                                                                
    {                                                                                               
        printf("%d\n", second1);                                                                      
    }                                                                                                                                                  
    else if (second2 != -1)                                                                           
    {                                                                                               
        printf("%d\n", second2);                                                                      
    }                                                                                                                                               
    else if (second3 != -1)                                                                           
    {                                                                                               
        printf("%d\n", second3);                                                                      
    }                                                                                               

    return 0;                                                                                       
}   

Answer 1

I would expect main to look like

int main(void)
{                                             
    int a, b, c;

    scanf("%d %d %d", &a, &b, &c);

    printf("%d\n", find_second(a, b, c));
}

Obviously your original function wouldn't work with this, but it's much more straight forward. Read in the input, process it, output the results.

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void sort(int *a, int *b, int *c)
{
    if (*a > *b)
    {
        swap(a, b);
    }

    /* a <= b now */
    if (*b > *c)
    {
        swap(b, c);

        if (*a > *b)
        {
            swap(a, b);
        }
    }
    /* a <= b <= c */
}

int find_second(int a, int b, int c)
{
    sort(&a, &b, &c);

    return b;
}

Hopefully swap is clear. It just exchanges the two values.

The sort function now sorts the three values such that afterwards, \$a \le b\$ and \$b \le c\$. It may seem like you are checking a and b twice, but realize that they could change in between. So the second time you could be comparing the original a or b to the original c.

Once sorted, we can just return b, which is the middle value.

In my opinion, this is the most readable version. You might be able to get better performance by multiplying or taking the exclusive or, but this is the most understandable.

I'm also not convinced that it is slower. Note that a ^ b ^ c ^ smallest ^ largest does four register assignments (of intermediate results) and min and max each do two comparisons and two register assignments. At worst, this version does three comparisons and nine register assignments. At best, this version does no assignments and two comparisons. The min/max solutions always do at least four comparisons and eight assignments. In many systems, each if comparison involves a register assignment and then a branch command. So four branches against three.

You'd have to test to be sure how each version performed. Note that you'd likely have to do a large number of operations to get a good test, as both versions are going to be very fast on an individual basis. Actual speed may depend on how the compiler is able to optimize them.

An alternative is to use an array instead.

int compare_int(const void *a, const void *b)
{
   return ( *(int *)b - *(int *)a );
}

int find_second(int *data, int size)
{
    qsort(data, size, sizeof *data, compare_int);

    return data[1];
}

int main(void)
{                                             
    int data[3];

    scanf("%d %d %d", &data[0], &data[1], &data[2]);

    printf("%d\n", find_second(data, 3));
}

This allows us to use the standard qsort and avoid defining our own sort.

It also scales well. It's easy to return a different ordinal value or to handle more values.

Answer 2

Your find_second() function is rather weird. It never finds the second-largest number if it is a. It sometimes finds the second-largest number if it is b or c. I don't know if your program works or not — your main() tries to make up for the deficiencies in find_second() by calling it three times — but the function name is a big fat lie.

Special numbers that might also be valid data are dangerous. What if the second-largest number happens to be -1?

For a solution that is easier to verify, I recommend this approach. min() and max() are trivial to write.

int second_largest(int a, int b, int c) {
    int smallest = min(min(a, b), c);
    int largest = max(max(a, b), c);

    /* Toss all three numbers into a bag, then exclude the
       minimum and the maximum */
    return a ^ b ^ c ^ smallest ^ largest;
}

Answer 3

Strange return value

Why does find_second() ever return -1? That function should actually find the second value, even if it had to loop three times within the function to do so. It doesn't make sense to call it three times from main().

Minimal comparisons

Most of the other answers gave alternate solutions where you had to do four comparisons followed by some math operations. The minimal solution requires only three comparisons, and can sometimes return after two. It also doesn't need any other math operations:

int find_second(int a, int b, int c)
{
    if (a > b) {
        if (c > a)
            return a;
        if (b > c)
            return b;
    } else {
        if (c > b)
            return b;
        if (a > c)
            return a;
    }
    return c;
}

Answer 4

One more way to find the second maximum value among the 3 given values is to add all three numbers and remove the maximum and minimum values.

$$ Second.largest(a,b,c)=a+b+c-max(a,b,c)-min(a,b,c) $$

This would be the function:

int find_second(int a, int b, int c)
{
    return a+b+c-max(a,b,c)-min(a,b,c);
}

Here max() and min() are the functions to find maximum and minimum values among 3 numbers respectively.

Answer 5

I am not particularly strong in C++, bu here are my two cents. Finding the next biggest number when you have 3 numbers is the same as finding the middle number.

Finding the biggest number can be found by max(a, b, c) similarly the minimum is min(a, b, c). So the middle number is

$$ \text{secondBiggest(a,b,c)} = \frac{abc}{\min(a,c,b)\cdot \max(a,b,c)} $$

If you are doing this with a list instead see https://stackoverflow.com/questions/2392689/how-can-we-find-second-maximum-from-array-efficiently

This can be coded as.

#include <stdio.h>                                                                                                                                                                                                                                                                                

int find_second(int a, int b, int c) {                                                                                                                                                                                                                                                 
    return a*b*c/((std::min({a, b, c}))*(std::max({a, b, c}));                                                                                                                                                                       

int main(void)                                                                                      
{                                                                                                                                             
    int a, b, c, second;                                                               

    scanf("%d %d %d", &a, &b, &c);                                                                  

    second = find_second(a, b, c);                                                                

    printf("%d\n", second);      

    return 0;                                                                                       
}   

Answer 6

Since you were looking for performance and readability, JS1 has already solved it for you; the result is readable, and using 2 or 3 comparisons, pretty fast. Trying to make it faster will likely make it less readable. I just wanted to add a couple of comments:

• You use a flag of -1 for a failure in the original function. You have to decide when such a failure exists - for example, if I enter 1,1,1 what exactly is the second lowest number to be? If you allow 1 as the answer, it's not correct, but may be safe for whatever use you want the function put to. However, if you want the return to always be mathematically the second highest number, then you may wish to include a flag return on failure, like the -1 you already use.

• Based on that, you have four return possibilities: a, b, c or -1 (error). Very simple code to handle that would be:

  int find_second(int a, int b, int c)
  {
    if ( a==b || a==c || b==c ) // eliminate problem cases ASAP
      return -1;
    /*
    eliminating equalities, we are now left with these possibilities:
    a > b > c
    a > c > b
    b > a > c
    b > c > a
    c > a > b
    c > b > a
    */
    if (a > b) 
    {
      // here must be  a > b > c  or  a > c > b  or  c > a > b  
      if (c > a)
        return a; // c > a > b        
      // remaining: a > b > c  or  a > c > b  
      if (b > c) 
        return b; // a > b > c
      return c; // a > c > b
    }
    // b > a,  so now must be  b > a > c  or  b > c > a  or  c > b > a
    if (c > b)
      return b; // c > b > a
    // remaining: b > a > c  or  b > c > a 
    if (c > a)
      return c; //  b > c > a
    return a; // b > a > c   
  

I've commented it to help explain the process.

One caution - this code is for three items, and does fine with readability and performance - however, it fails for 'extendability' - try to extend it for four, five or six items and you'll end up rewriting much of the code...

Answer 7

I came up with this answer independently but it is effectively the same as JS1's (so upvote that one not mine), but written slightly differently. Generally I prefer not to use else when an if statement is guaranteed to return and I prefer ternary ?: syntax when it's simple to understand over if/else.

int find_median(int a, int b, int c) {
    if (a < b) {
        if (b < c) return b;                // a b c
        if (c < a) return a;                // c a b
        return c;                           // a c b
    }
    if (b < c) return a < c ? a : c;        // b a c : b c a

    return b;                               // c b a
}

This method results in three comparisons at most (obviously some assumptions are made about inputs but that was stated in the question), no function calls, and no wasted instructions dereferencing pointers or storing variables. It is vastly superior to any of the methods that require sorting. Again, this was put forth before me by JS1 so I feel his/her answer should be the accepted one.

Answer 8

You can also use the C feature that the comparison operators returning 1 on success and 0 on failure. With this you can implement it like:

int sl(int const a, int const b, int const c) {
    _Bool const a_less_b = (a < b);
    switch(a_less_b + (b < c) + (a < c)) {
        case 0: // sorted
        case 3: return b; // reverse
        case 1: return a_less_b ? a : c;
        case 2: return a_less_b ? c : a;
    }
}

This solution needs no swap and three comparison '<' calls. Maybe it is faster than the other ones. See live demo

Answer 9

I think the best way is to sort the numbers in an array then print the middle one

Here I have coded in Java Environment and used bubble sort technique.

public static void main (String[] args) throws java.lang.Exception
{
    int A[]=new int[3];
    System.out.print("Enter 3 Numbers: ");
    int temp=0;
    for(int i=0;i<3;i++)
    {
        A[i]=Integer.parseInt(br.readLine());
    }
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(A[j]>A[j++])
            {
                temp=A[j++];
                A[j++]=A[j];
                A[j]=temp;
            }
        }
    }
    System.out.println("SECOND LARGEST: "+A[1]);
}

}