Valhalla Legends Forums Archive | General Programming | Minimum and Maximum of 3 integers

AuthorMessageTime
TangoFour
I think one of my teachers once mentioned it, but I can't seem to figure it out:

Is there a way to determine the Minimum and Maximum of 3 integers with just 2 equations?

Let's say we have 3 integers:

a = 14
b = 1337
c = 666

Can I determine the minimum and maximum with just 2 equations?
December 7, 2004, 9:53 PM
iago
It depends how you define equations.  You can do it with 2 if's:
int a = 14;
int b = 1337;
int c = 666;
int max = a;
int min = a;
if(max < b || max < c)
  max = b < c ? c : b;
if(min > b || min > c)
  min = b > c ? c : b;

At this point, the max and min will be in the proper variables, unless I made a logical mistake.  And it uses 2 if statements, technically. :)
December 7, 2004, 10:18 PM
TangoFour
With equations I meant comparisons between 2 integers
December 7, 2004, 10:35 PM
Yoni
iago's code uses 6 comparisons.
It can be done easily with 3 comparisons.

You can't guarantee being able to do it with less than 3 comparisons.
That is, you can do it with 2, but not always. This can be proven mathematically.
(I didn't consider comparisons of sizes that aren't a,b,c, like a+b>c. I think it still can't be done with 2 comparisons but can't prove it right now.)

Riddle: It is possible to find the minimum and maximum of an array of n integers at the same time using only (1.5n + Const) comparisons, instead of the obvious "find minimum, then find maximum" which takes (2n + Const) comparisons. How?

Edit: Wrote "Const" instead of O(1) in case some readers are unfamiliar with the O notation.
December 7, 2004, 11:47 PM
iago
He said "2 EQUATIONS", not comparisons! :P
December 8, 2004, 1:38 AM
TangoFour
I meant comparisons, I stated that in my reply, sorry for being unclear Iago  ;)
December 8, 2004, 9:36 AM
Adron
Here it's done in a single equation:

((max = a) || 1) && ((max < b) || (max = b) || 1) && ((max < c) || (max = c) || 1) && ((min = a) || 1) && ((min > b) || (min = b) || 1) && ((min > c) || (min = c) || 1);


:P
December 8, 2004, 11:31 PM

Search