Most Efficient Way to Find the Greatest of Three Ints

Most efficient way to find the greatest of three ints

To find the greatest you need to look at exactly 3 ints, no more no less. You're looking at 6 with 3 compares. You should be able to do it in 3 and 2 compares.

int ret = max(i,j);
ret = max(ret, k);
return ret;

Write a program that will take three integers as input and will print the second largest number

This is not the Logic which you can understand, it'll not give you the right, expected result.

Code:

#include <stdio.h>

int main()
{
    int a, b, c;
    printf("Values: ");
    scanf("%d%d%d", &a, &b, &c);
    if(a>b && a>c)
    {
        if(b>c)
            printf("2nd largest: %d", b);
        else
            printf("2nd largest: %d", c);
    }
    else if(b>c && b>a)
    {
        if(c>a)
            printf("2nd largest: %d", c);
        else
            printf("2nd largest: %d", a);
    }
    else if(a>b)
            printf("2nd largest: %d", a);
        else
            printf("2nd largest: %d", b);
    return 0;
}

You should compare all the three variables to get the 2nd largest among those numbers.

Output:

Values: 32 31 12
2nd largest: 31

Explanation:

First pick any variable and compare it with the other two variables like if(a>b && a>c), if its true, it means a is the largest and any of the two variables b and c is the 2nd largest, so inside the if(a>b && a>c) block there's a comparison if(b>c), if true then b is the 2nd largest otherwise c is the second largest. Similarly, compare the other two variables for if they are the largest. e.g. else if(b>c && b>a) and else if(c>a && c>b).

Most efficient way to get the highest number from a collection of integers

If the Collection is already sorted, you can find the largest element in O(1) (assuming the Collection supports random access or O(1) access to the end of the Collection holding the largest element - if the largest element is first, any Collections would give you an O(1) access to it via its Iterator). In that case you don't have to sort it, though.

Any sorting would take at least O(n) when the input is sorted (and at least O(nlog(n)) when it's not), since you can't verify that the input is sorted without going over all the elements. Therefore sorting algorithms cannot beat your O(n) solution.

Simpler way of sorting three numbers

if (a > c)
   swap(a, c);

if (a > b)
   swap(a, b);

//Now the smallest element is the 1st one. Just check the 2nd and 3rd

if (b > c)
   swap(b, c);

Note: Swap changes the values of two
variables.

Is there a method to find the max of 3 numbers in C#?

Well, you can just call it twice:

int max3 = Math.Max(x, Math.Max(y, z));

If you find yourself doing this a lot, you could always write your own helper method... I would be happy enough seeing this in my code base once, but not regularly.

(Note that this is likely to be more efficient than Andrew's LINQ-based answer - but obviously the more elements you have the more appealing the LINQ approach is.)

EDIT: A "best of both worlds" approach might be to have a custom set of methods either way:

public static class MoreMath
{
    // This method only exists for consistency, so you can *always* call
    // MoreMath.Max instead of alternating between MoreMath.Max and Math.Max
    // depending on your argument count.
    public static int Max(int x, int y)
    {
        return Math.Max(x, y);
    }

    public static int Max(int x, int y, int z)
    {
        // Or inline it as x < y ? (y < z ? z : y) : (x < z ? z : x);
        // Time it before micro-optimizing though!
        return Math.Max(x, Math.Max(y, z));
    }

    public static int Max(int w, int x, int y, int z)
    {
        return Math.Max(w, Math.Max(x, Math.Max(y, z)));
    }

    public static int Max(params int[] values)
    {
        return Enumerable.Max(values);
    }
}

That way you can write MoreMath.Max(1, 2, 3) or MoreMath.Max(1, 2, 3, 4) without the overhead of array creation, but still write MoreMath.Max(1, 2, 3, 4, 5, 6) for nice readable and consistent code when you don't mind the overhead.

I personally find that more readable than the explicit array creation of the LINQ approach.

find the highest product you can get from three of the integers in an array - how to solve using brute force

Using three for loops :

public static Integer highestProduct(int array[]) 
{
    if((array==null)||(array.length<3))
    {
        return null;
    }

    else
    {
        int max_product = Integer.MIN_VALUE;
        for(int i=0;i<array.length;i++)
        {
            for(int j=i+1;j<array.length;j++)
            {
                for(int k=j+1;k<array.length;k++)
                {
                    int product = array[i]*array[j]*array[k];
                    if(product>=max_product)
                    {
                        max_product = product;
                    }
                }
            }
        }
        return max_product;
     }
 }

Most efficient way to find median of three integers

The fastest way I know of is to use

max(min(a, b), min(max(a, b), c))

I'm trusting that C# has optimisations for min and max taking two arguments. This will be quicker than taking if statements due to branching.

There are other tricks: you can implement min and max using XOR and < but I doubt that has any benefits on modern architectures.

Fastest way of finding the middle value of a triple?

If you are looking for the most efficient solution, I would imagine that it is something like this:

if (array[randomIndexA] > array[randomIndexB]) {
  if (array[randomIndexB] > array[randomIndexC]) {
    return "b is the middle value";
  } else if (array[randomIndexA] > array[randomIndexC]) {
    return "c is the middle value";
  } else {
    return "a is the middle value";
  }
} else {
  if (array[randomIndexA] > array[randomIndexC]) {
    return "a is the middle value";
  } else if (array[randomIndexB] > array[randomIndexC]) {
    return "c is the middle value";
  } else {
    return "b is the middle value";
  }
}

This approach requires at least two and at most three comparisons. It deliberately ignores the possibility of two values being equal (as did your question): if this is important, the approach can be extended to check this also.

---

Related Topics