Author | Message | Time |
---|---|---|
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 |