The smallest, largest and average of array of n size

The interview question was something like this:

Given an array of some numbersnhow will you find thesmallestlargestand theaverage?

The answer that I made wassorting the elements of the arrayand thefirstelement would be thesmallestandlastwould be thelargest.

But I was told by the interviewer that sorting (assuming it takesO(n), to find average it might take againO(n)). And she added thatshe wanted a solution without sorting.

Any ideas how to do this inoptimally?. Is there any pre defined algorithm that applies to this case?

(Though I am comfortable with anyC/C++/Javaanswers or evenpseudo codes, any answers inC#is much appreciated).

I would just iterate through the array, keeping track of the total, and check at each iteration if the value is smaller than the minimum, or greater than the maximum, and if so, store those as the new min/max. Average is then just dividing total by the # of items in the array. That should require only O(n) to do.

An O(n) algorithm would look like this, no sorting at all:

public class Program
{
    public void Main()
    {
        int[] arr = {4, 8, 9, 13, -9, 78, 5};
        FindMinAvgMax(arr);
    }

    public void FindMinAvgMax(int[] a)
    {
        int len = a.Length;
        int sum = 0;
        int min = a[0];
        int max = a[0];
        int avg;

        for(int i = 0; i < len; i++)
        {
            sum += a[i];

            if(a[i] < min)
                min = a[i];
            else if(a[i] > max)
                max = a[i];
        }

        avg = sum /len;

        Console.WriteLine("Min: {0}", min);
        Console.WriteLine("Max: {0}", max);
        Console.WriteLine("Avg: {0}", avg);
    }
}

Live demo:http://dotnetfiddle.net/4Bz80E

The following code does it with complexity of O(n), while sorting will take O(n* log(n))

static void FindLagestSmalestAvg(int[] array)
{
    int smallest = array[0];
    int largest = array[0];
    int sum = 0;

    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] > largest)
            largest = array[i];

        if (array[i] < smallest)
            smallest = array[i];

        sum += array[i];
    }

    int average = sum / array.Length;

    Console.WriteLine("Smallest = {0}, largest = {1}, average = {2}", smallest, largest, average);
}

An interviewer generally expects logic, not shortcuts, because all shortcuts work internally using big logic only, so you should follow the below steps.

This takes O(n).

  1. For loop with n times

  2. Take first number and compare with all other number, here you will get small and large number

  3. At same time use another variable to add all numbers inside that same for loop

  4. After for loop you will get smallest, largest as well as addition of all number

  5. Then you know to find average(addition/n)...

Here's some code that does this:

static void Main(string[] args)
{
    int[] a = { 1, 90, 3, 4, 0, 6 };
    int small,big;
    float avg=0;

    small = a[0];
    big = a[0];

    for (int i = 0; i < a.Length; i++) //O(n) executed n times only
    {
        if (small > a[i])
            small = a[i];
        if (big < a[i])
            big = a[i];
        avg += a[i];
    }
    avg = avg / a.Length;

    Console.WriteLine("smallest= " + small + "  largest= " + big + "  Average= " + avg);
    Console.ReadKey();
}
public void find(int[] a)
{

    int sum = 0;
    int min = 9999999; // any very big int
    int max = -999999; // any smallest int
    int i = 0;
    for(i = 0; i < a.length; i++)
    {
        if(a[i] < min)
            min = a[i];
        if(a[i] > max)
            max = a[i];
        sum+=a[i];
    }

    avg = sum /i;
    // min will contain smallest num, max will contain largest and avg is avgerage
}
What Others Are Reading