Mayur Kulkarni - 9 months ago 50

Java Question

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.