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;

Answer 2

He was probably referring to the fact that you don't need all the terms to compute an average, you can instead keep track of a moving average. That can be used along with the number of terms so far considered to come up with the sum of the terms.

Since the total could be too large to store as a long, you'd want to use something like a BigInteger to hold the total.

Answer 3

If you simplify rgettman's formula further you will get following:

len++;
average = average + (it.next() - average) / len;