Tuesday, February 21, 2012

Find the average

Given a set of n numbers (data type long). Write an algorithm to get the average.
  • 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.
Strategy:
We can’t use addition for getting the average. If we do, first constraint might not get incorporated.We have to work with an equation.
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 everytime we hit an uneven divide and there is a loss of precision.

Alternatively,
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;
}

No comments:

Post a Comment