The interview question was something like this:

Given an array of some numbers`n`

how will you find the`smallest`

`largest`

and the`average`

?

The answer that I made was`sorting the elements of the array`

and the`first`

element would be the`smallest`

and`last`

would be the`largest`

.

But I was told by the interviewer that sorting (assuming it takes`O(n)`

, to find average it might take again`O(n)`

). And she added that`she wanted a solution without sorting`

.

Any ideas how to do this in`optimally?`

. Is there any pre defined algorithm that applies to this case?

(Though I am comfortable with any`C`

/`C++`

/`Java`

answers or even`pseudo codes`

, any answers inis much appreciated).

`C#`

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).

For loop with n times

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

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

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

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
}
```