How to get the largest and smallest of 3 values with fewest comparisons?

c++ if-statement

45,466

Solution 1

The issue with your code is that you toss out a lot of information. In "challenges" such as these, you have to make the most of what you have. So when you say, for example

if (y > largest)

don't just treat the true case. Also try to reason about the case when the condition doesn't hold.

if ( x < y )
{
    smallest = x;
    biggest = y;
}
else
{
    smallest = y;
    biggest = x;
}

if ( z < smallest )
   smallest = z;
else if ( z > biggest )
   biggest = z;

This contains only 3 comparisons.

Solution 2

The question is finding the largest or smallest by only if else statements, and we have three variables to use, so we only need two comparisons.

{
    int valueOne,
    valueTwo,
    valueThree,
    smallest;

//User input for valueOne, valueTwo, valueThree.

smallest = valueOne;

if (smallest < valueTwo)
{
smallest = valueTwo;
}
if (smallest < valueThree)
{
smallest = valueThree;
}

//No matter what happens, smallest will have the smallest value now.

//Use >, rather than <, and "largest" rather than "smallest" for finding largest value.

//With this logic, you always will have one less comparison than the total number or variables to compare

//i.e. 7 variables means 6 comparisons.

//This contains only 2 comparisons.

Solution 3

Why are you checking if (y < smallest)? At this point in the flow, smallest must be x, but you've already checked if y > x in the first condition (if (y > largest)), so the third condition is redundant.

45,466

Author by

George

Updated on November 05, 2020

Comments

George over 3 years
This is a simple introduction course question. I have to write a program that asks the user to input 3 numbers, and determines the largest and smallest number.

I need to only use if statements.

This is what I tried so far: which required 4 comparisons.
```
int x, y, z;
int smallest, largest; 
cout << "Please enter 3 numbers to compare: " ;
cin >> x >> y >> z;

smallest = x;
largest = x;

if (y > largest) 
        largest = y;
if (z > largest)
        largest = z;
if (y < smallest)
        smallest = y;
if (z < smallest)
        smallest = z;

cout << "largest: " << largest << ", and smallest: " << smallest << endl;   
```
My question is: Is it possible to only use 3 comparisons, or less? I think when y > largest, it also tells us something else as well?
Mooing Duck almost 11 years

I'm pretty sure if z is biggest three comparisons get executed.
Ilya Kogan almost 11 years

Sure, just start with largest = y instead of largest = x and see where it takes you...
George almost 11 years

@LuchianGrigore I don't know if it matters, but if it is only if statement, no else statement. Can it also be done in 3 comparison?
Luchian Grigore almost 11 years

@George the else is part of the if statement.
George almost 11 years

@LuchianGrigore I know, but that's because this question came in the chapter before the book teaches else statement, I was just wondering.
BatchyX almost 11 years

@George: If your exercise is limited to that, just put the first else part before the if (so it gets executed every time, but if the if condition is true, the values are overwritten), and drop the other else which is just an optimization.
kotlomoy almost 11 years

It works only if long is 64bit. Not too many places where it will work. I never saw such places, for example
SirGuy almost 11 years

@kotlomoy long is 64 bits on Linux, but not Windows. There are defines for different data types for Windows that you can use instead. I'm not sure what it is offhand though.
SirGuy almost 11 years

@kotlomoy changed long to int64_t defined in stdint.h. That should make it work on Windows as well (not that I'm able to test that, however)
Zyx 2000 almost 11 years

Preferrably <cstdint> instead of <stdint.h>, since this is a C++ question.
SirGuy almost 11 years

<cstdint> is actually c++11, it was actually the first thing I tried.