Wednesday, May 7, 2014

Find the average of n numbers

Problem


Given a set of n numbers (data type long). Write an algorithm to get the average.
Constraints
  • It should work if one of the contributing number is the maximum possible number of type long.
  • Casting it to other data types is not allowed.

Solution

We can’t use addition for getting the average. If we do, first constraint might not get incorporated as we may overflow. .We have to work with an equation.
Method 1 - Average with difference Keep looping till you hit the last number. Counter is the index variable for the loop that increments by one at each iteration.

average = average + (nextNumber – average)/counter

We have to round of every-time we hit an uneven divide and there is a loss of precision.

Method 2 - Average with divide
divide each number by n individually and then add up all of them.
like this average of a,b,c is –
average = a/3 + b/3 + c/3;
you can do it while traversing –
long average = 0
for(i = 1 to n ; i++)
{
 nextNumber = inputSet[i];
 average = average + nextNumber/ n;
}

References

0 comments:

Post a Comment