Mayur Kulkarni Mayur Kulkarni - 5 months ago 26
Java Question

Erroneous behaviour of Java 8 Stream.sum()

Today while solving this question on HackerRank I used Array stream .sum() function to sum all the entries and proceeded with my algorithm. But for sum reason I found that my algorithm fails for some cases. I used diff to find out it passes 99% cases and for 1% the output is nearly equal but is less than the original answer. That's why I replaced the stream .sum() with a for loop and unexpectedly it passed all the test cases. I tried but couldn't ascertain this uncertain behaviour.

My implementation using stream.sum() :

public class MandragoraForest {

public static void main(String[] args) {
InputReader in = new InputReader(System.in);
for (int i = in.nextInt(); i > 0; i--) {
int number = in.nextInt();
int[] h = new int[number];
for (int j = 0; j < number; j++) h[j] = in.nextInt();
System.out.println(new MandragoraForestSolver().solve(h));
}
}
}

class MandragoraForestSolver {

public long solve(int[] h) {
if (h.length==1) return h[0];
Arrays.parallelSort(h);
long sum = Arrays.stream(h)
.sum();
long ans = -1;

for (long i=0, strength = 2; i<h.length; i++, strength++) {
sum -= h[(int)i];
ans = Math.max(ans, strength * sum);
}
return ans;
}
}


Implementation without Java stream :

public class MandragoraForest {

public static void main(String[] args) {
InputReader in = new InputReader(System.in);
for (int i = in.nextInt(); i > 0; i--) {
int number = in.nextInt();
int[] h = new int[number];
long sum = 0;
for (int j = 0; j < number; j++) {
h[j] = in.nextInt();
sum += h[j];
}
System.out.println(new MandragoraForestSolver().solve(h, sum));
}
}
}

class MandragoraForestSolver {

public long solve(int[] h, long sum) {
if (h.length==1) return h[0];
Arrays.parallelSort(h);


long ans = -1;

for (long i=0, strength = 2; i<h.length; i++, strength++) {
sum -= h[(int)i];
ans = Math.max(ans, strength * sum);
}
return ans;
}
}


Is there something that I'am missing out ? What could be the reason for this behaviour?

Answer

There is one significant difference between using a stream and a loop - the possibility of arithmetic overflow.

Arrays.stream(int[]) returns an IntStream, whose sum() method returns an int result. If the sum exceeds Integer.MAX_VALUE, a silent integer overflow will occur.

However your loop sums by adding int values to a long total, which would not suffer from arithmetic overflow.

The sum of integers in one of the tests must exceed Integer.MAX_VALUE, testing that a long is used to (correctly) calculate the total.


If you want to use a stream to sum, you need to convert the IntStream to a LongStream, which you can do like this:

long sum = Arrays.stream(big).mapToLong(i -> i).sum();

There's no need to cast - Java will do an automatic (safe) widening cast from int to long in the mapping lambda.