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?

related questions: http://stackoverflow.com/questions/1657834/how-can-i-check-if-multiplying-two-numbers-in-java-will-cause-an-overflow http://stackoverflow.com/questions/12226634/how-to-prevent-integer-overflow-in-java-code — Mike R, Apr 23 '14 at 19:42
You wrote "to compute the sum", you meant the average, right? — icza, Apr 23 '14 at 20:32

score 3 · Accepted Answer · answered Apr 23 '14 at 19:55

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;

score 2 · Answer 2 · answered Apr 23 '14 at 19:46

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.

answered Apr 23 '14 at 19:46

azurefrog

10,785
7
42
56

Can you elaborate more on this, because he did mention BigDecimal and then moved on movingAverage for his next question. – user1529412 Apr 23 '14 at 19:56

score 2 · Answer 3 · answered Apr 23 '14 at 20:02

2

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

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

answered Apr 23 '14 at 20:02

hoaz

9,883
4
42
53

Overflow of integer in Java

3 Answers3