15
\$\begingroup\$

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;                                                                                       
}   
\$\endgroup\$
  • 1
    \$\begingroup\$ How are you handling cases like 1,1,1 or 1,2,2 ? You return -1 that's obviously, but what I'd expect is 1 for the first case and 1 for the second one. \$\endgroup\$ – Grajdeanu Alex. Jun 24 '16 at 21:28
  • \$\begingroup\$ Oh, sorry! I forgot to say that the problem tells me that all of the numbers are different. \$\endgroup\$ – Lúcio Cardoso Jun 24 '16 at 21:48
  • 1
    \$\begingroup\$ After answering Dex'ter's question, try to do it in the fewest possible comparisons; that will be fastest. Start by stepping through and counting the number of comparisons (< operations) performed by your current code, on average and in the worst case. Can you do it in fewer? \$\endgroup\$ – Quuxplusone Jun 24 '16 at 21:49
  • 1
    \$\begingroup\$ How do you handle a = b = c = -1 ? \$\endgroup\$ – gnasher729 Jun 25 '16 at 8:36
  • \$\begingroup\$ In the edit, I said "assuming the numbers are always positive" (even though I know this solution wasn't reall clever) \$\endgroup\$ – Lúcio Cardoso Jun 25 '16 at 21:54
11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Perhaps you meant sort(&a, &b, &c);? \$\endgroup\$ – chux Jun 25 '16 at 3:10
  • 2
    \$\begingroup\$ Not a issue for OP's [1..100] yet ( *(int *)b - *(int *)a ); otherwise can overflow. Suggest return ( *(int *)b > *(int *)a ) - ( *(int *)b < *(int *)a ) \$\endgroup\$ – chux Jun 25 '16 at 3:13
  • \$\begingroup\$ +1 because this approach works for generic comparables, instead of just ints (or numbers). Also, it scales to sequences of generic length. This should be the accepted answer, in my opinion. \$\endgroup\$ – Sjoerd Job Postmus Jun 25 '16 at 6:00
  • \$\begingroup\$ @Sjoerd Job Postmus When using FP numbers that allow Not-A-numbers, problems occur with direct application of the above methods. NaNs are usually considered to be not part of the set of number to "find the second greatest of them". So { 1, NaN, 2 } --> 1 (the 2nd greatest). Integers are well ordered, other types have their idiosyncrasies. \$\endgroup\$ – chux Jun 26 '16 at 16:15
  • \$\begingroup\$ @chux: the moment the set is not well-ordered, does it even make sense to talk about the second largest element? I probably should have be more specific about what it working for other well ordered types instead of "comparables" \$\endgroup\$ – Sjoerd Job Postmus Jun 26 '16 at 20:10
29
\$\begingroup\$

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;
}
\$\endgroup\$
  • 7
    \$\begingroup\$ This looks awesome: int second = x ^ y ^ z ^ first ^ third;. And evil. Both at the same time. \$\endgroup\$ – Grajdeanu Alex. Jun 24 '16 at 22:02
  • \$\begingroup\$ Thanks a lot! And thank you even more for spotting those dangerous mistakes. I forgot to explain that in the question, but the problem also tells us to assume the input is always positive. \$\endgroup\$ – Lúcio Cardoso Jun 24 '16 at 22:06
  • \$\begingroup\$ Either way, why limit yourself, when you could write a function that works in the general case? \$\endgroup\$ – 200_success Jun 24 '16 at 22:13
  • 4
    \$\begingroup\$ Nice one. You can write the last line as : a + b + c - smallest - largest, if you want to make it more clear for everyone. \$\endgroup\$ – Rick Sanchez Jun 25 '16 at 11:45
  • 2
    \$\begingroup\$ @RickSanchez Unfortunately that can overflow an int. \$\endgroup\$ – skiwi Jun 25 '16 at 13:39
16
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Great! Very simple solution. By I have a question: Is it fast? \$\endgroup\$ – Lúcio Cardoso Jun 26 '16 at 16:14
  • 2
    \$\begingroup\$ This is certainly fast and should be the accepted answer. \$\endgroup\$ – chux Jun 26 '16 at 16:44
  • 2
    \$\begingroup\$ @LúcioCardoso i don't see how it could be faster than this. \$\endgroup\$ – JS1 Jun 26 '16 at 21:22
  • 1
    \$\begingroup\$ It can't be faster than this because there's no way around comparing each value to each of the others. This solution does that using the minimal amount of work/overhead and is therefore best. Although, as some of the other answers demonstrate, the implementation can definitely be slower :) \$\endgroup\$ – par Jun 26 '16 at 23:15
6
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Adding signed ints could cause overflow and undefined behaviour. \$\endgroup\$ – 200_success Jun 24 '16 at 23:56
  • \$\begingroup\$ OP said they were positive and less than 100, so not a problem. \$\endgroup\$ – Ross Millikan Jun 25 '16 at 4:10
  • \$\begingroup\$ @200_success ... Ya the OP mentioned all the numbers are less than 100... So I think there's no problem of overflow \$\endgroup\$ – Cherubim Jun 25 '16 at 4:29
  • 1
    \$\begingroup\$ Yes, that information was added in Rev 3. I stand corrected. \$\endgroup\$ – 200_success Jun 25 '16 at 4:31
5
\$\begingroup\$

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;                                                                                       
}   
\$\endgroup\$
  • 6
    \$\begingroup\$ Multiplying three ints together with * can easily overflow the maximum representable value of an int. So can adding them together with +, for that matter. Can you find a commutative, associative, invertible operation that does not have these problems? (Hint: if you try all the built-in C operators in order, you will eventually find it.) \$\endgroup\$ – Quuxplusone Jun 24 '16 at 21:59
  • \$\begingroup\$ I totally agree. This was just to give some ideas to Lúcio Cardoso. Using comparisons with max and min should quickly yield the answer. \$\endgroup\$ – N3buchadnezzar Jun 24 '16 at 22:02
  • 1
    \$\begingroup\$ By the way, I think it's also valid to point out that the problem also explains the maximum size of a, b and c is 100. \$\endgroup\$ – Lúcio Cardoso Jun 24 '16 at 22:10
  • 1
    \$\begingroup\$ @LúcioCardoso Technically, it could still overflow if int is a 16-bit signed integer, which is what the C specification guarantees. \$\endgroup\$ – 200_success Jun 25 '16 at 1:54
  • \$\begingroup\$ And what if one of the numbers is 0? Then min() will return 0 and the division will fail. This is no solution if you have to assume certain values for the input. \$\endgroup\$ – user1016274 Jun 25 '16 at 10:34
2
\$\begingroup\$

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...

\$\endgroup\$
  • \$\begingroup\$ I did want to point out in I know the requirements stipulate that no input numbers are equal to any other - however, this code shows what could be done if two of the numbers might be equal, something I think would happen often in production code. \$\endgroup\$ – Dave P. Jun 26 '16 at 8:34
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I would also find the @JS1 answer easier to read than this. Note that it uses the else because it isn't guaranteed to return. \$\endgroup\$ – mdfst13 Jun 26 '16 at 22:19
  • \$\begingroup\$ All the if statements I used are guaranteed to return. But it is truly a matter of style. Since this is a code review site I think demonstrating a variety of styles can be useful. \$\endgroup\$ – par Jun 26 '16 at 22:58
  • \$\begingroup\$ I'll also criticize JS1's answer in a very minor way by noting that his/her code will get to the final statement of return c; when the input is either a < c < b or b < c < a. The code is correct, but I find that marginally more confusing than my approach where each possible arrangement of a, b, and c has exactly one distinct & separate code path to the return value. Again, it's just a matter of preference & style. \$\endgroup\$ – par Jun 26 '16 at 23:09
  • 1
    \$\begingroup\$ @par My original version had two "return c" lines, one in the top part and one in the bottom part. Then I decided that I could save a line by moving both of those lines out and putting one line at the end of the function. I also experimented with not having an else statement but it looked "unbalanced" so I just left it in. It's totally a matter of preference/style. \$\endgroup\$ – JS1 Jun 27 '16 at 21:59
2
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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]);
}

}

\$\endgroup\$
  • 2
    \$\begingroup\$ As a general rule, please stick to the language in the question. Also, we are more focused on review than code. The base insight here has already been posted. And worst, your solution is wrong. You say A[j++] three times when you should be saying A[j+1]. \$\endgroup\$ – mdfst13 Jun 25 '16 at 12:08
  • \$\begingroup\$ @mdfst13 Indeed. If you wanted a different language, a functional one would be better (secondHighest = head . tail . sort), but that's clearly not what the OP is after. He's also after high performance solution, which this quite clearly isn't. \$\endgroup\$ – Jules Jun 25 '16 at 13:52
  • \$\begingroup\$ @mdfst13: I agree completely. Furthermore, in my opinion, the code is "more" incorrect not because of the increment but because it is not simply Arrays.sort(xs). \$\endgroup\$ – wchargin Jun 26 '16 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.