16
\$\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\$
5
  • 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\$ Commented Jun 24, 2016 at 21:28
  • \$\begingroup\$ Oh, sorry! I forgot to say that the problem tells me that all of the numbers are different. \$\endgroup\$ Commented Jun 24, 2016 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\$ Commented Jun 24, 2016 at 21:49
  • 1
    \$\begingroup\$ How do you handle a = b = c = -1 ? \$\endgroup\$ Commented Jun 25, 2016 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\$ Commented Jun 25, 2016 at 21:54

9 Answers 9

Reset to default
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\$
5
  • \$\begingroup\$ Perhaps you meant sort(&a, &b, &c);? \$\endgroup\$ Commented Jun 25, 2016 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\$ Commented Jun 25, 2016 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\$ Commented Jun 25, 2016 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\$ Commented Jun 26, 2016 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\$ Commented Jun 26, 2016 at 20:10
30
\$\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\$
15
  • 8
    \$\begingroup\$ This looks awesome: int second = x ^ y ^ z ^ first ^ third;. And evil. Both at the same time. \$\endgroup\$ Commented Jun 24, 2016 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\$ Commented Jun 24, 2016 at 22:06
  • \$\begingroup\$ Either way, why limit yourself, when you could write a function that works in the general case? \$\endgroup\$ Commented Jun 24, 2016 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\$ Commented Jun 25, 2016 at 11:45
  • 3
    \$\begingroup\$ @RickSanchez Unfortunately that can overflow an int. \$\endgroup\$ Commented Jun 25, 2016 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\$
4
  • \$\begingroup\$ Great! Very simple solution. By I have a question: Is it fast? \$\endgroup\$ Commented Jun 26, 2016 at 16:14
  • 2
    \$\begingroup\$ This is certainly fast and should be the accepted answer. \$\endgroup\$ Commented Jun 26, 2016 at 16:44
  • 2
    \$\begingroup\$ @LúcioCardoso i don't see how it could be faster than this. \$\endgroup\$ Commented Jun 26, 2016 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\$ Commented Jun 26, 2016 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\$
4
  • 1
    \$\begingroup\$ Adding signed ints could cause overflow and undefined behaviour. \$\endgroup\$ Commented Jun 24, 2016 at 23:56
  • \$\begingroup\$ OP said they were positive and less than 100, so not a problem. \$\endgroup\$ Commented Jun 25, 2016 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\$ Commented Jun 25, 2016 at 4:29
  • 1
    \$\begingroup\$ Yes, that information was added in Rev 3. I stand corrected. \$\endgroup\$ Commented Jun 25, 2016 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
  • 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\$ Commented Jun 24, 2016 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\$ Commented Jun 24, 2016 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\$ Commented Jun 24, 2016 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\$ Commented Jun 25, 2016 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\$ Commented Jun 25, 2016 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\$
1
  • \$\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\$ Commented Jun 26, 2016 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\$
4
  • \$\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\$ Commented Jun 26, 2016 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\$ Commented Jun 26, 2016 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\$ Commented Jun 26, 2016 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\$ Commented Jun 27, 2016 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\$
3
  • 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\$ Commented Jun 25, 2016 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\$ Commented Jun 25, 2016 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\$ Commented Jun 26, 2016 at 5:26

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.