Overflow of integer in Java

Question

I was asked this in an interview. I was asked to compute the average of numbers x1,x2,x3,...xn

class Iterator {
    bool hasNext;
    int getNext();
}

// So it came down to something like this:

double average (Iterator & it) {

double average = 0;
double sum = 0;
int len = 0;

while (it.hasNext == true) {

    sum += it.getNext();
}

if (len > 0)
    average = sum / len;
}

The interviewer said the list size is unkown and it can be very big, so sum can overflow. He asked how do I solve the overflow problem, I answered by keeping track of how may times we exceed the max number and so forth, he said something about pushing into stack, the average and length, I never really understood his solution by pushing these 2 variables into some sort of list? Anyone has a clue?

Answer 1

I don't know about using a stack, but with some help from algebra, we can derive a formula for the new average, using the old average.

Let's say you have already averaged n - 1 items, and you have that average in oldAvg.

oldAvg = (x₁ + x₂ + .. + x_{n - 1}) / (n - 1)

The new average would be represented by newAvg:

newAvg = (x₁ + x₂ + .. + x_{n - 1} + x_n) / n

With some algebraic manipulation, we can represent the new average using the old average the number of items averaged, and the next item.

newAvg = (x₁ + x₂ + .. + x_{n - 1}) / n + x_n / n

= ((n - 1)/(n - 1)) * (x₁ + x₂ + .. + x_{n - 1}) / n + x_n / n

= oldAvg / n * (n - 1) + x_n / n

This can avoid overflow by dividing by n before multiplying by n - 1. Then all you have to do is add in the next item, x_n, divided by n.

The first loop would establish the average as equal to the first element, but each subsequent loop would use the formula above to derive the new average.

n++;
newAvg = oldAvg / n * (n - 1) + it.next() / n;