• Welcome to Valhalla Legends Archive.
 

Minimum and Maximum of 3 integers

Started by TangoFour, December 07, 2004, 03:53 PM

Previous topic - Next topic

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?

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. :)
This'll make an interesting test for broken AV:
QuoteX5O!P%@AP[4\PZX54(P^)7CC)7}$EICAR-STANDARD-ANTIVIRUS-TEST-FILE!$H+H*


TangoFour

With equations I meant comparisons between 2 integers

Yoni

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

iago

He said "2 EQUATIONS", not comparisons! :P
This'll make an interesting test for broken AV:
QuoteX5O!P%@AP[4\PZX54(P^)7CC)7}$EICAR-STANDARD-ANTIVIRUS-TEST-FILE!$H+H*


TangoFour

I meant comparisons, I stated that in my reply, sorry for being unclear iago  ;)

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