How to prevent overflow when calculating min & max sum of the elements by excluding one element in the list

Question

I need to find the minimum and maximum values that can be calculated by summing exactly (size - 1) elements in the arrays

Example:
arr = [1,2,3,4,5] minSum = 1+2+3+4 = 10 , maxSum = 2+3+4+5 = 14

Initially, I wrote the following code

public static void miniMaxSum(List<Integer> arr) {
    List<Integer> sorted = arr.stream().sorted().collect(Collectors.toList());
    Integer totalSum = sorted.stream().mapToInt(Integer::intValue).sum();
    Integer minSum = totalSum - sorted.get(sorted.size()-1);
    Integer maxSum = totalSum - sorted.get(0);
    System.out.println(minSum + " "+maxSum);
}

For the simple test cases, it is working as expected, but then for the numbers with higher value it is overflowing and resulting in negative values, so I used BigInteger.

public static void miniMaxSum(List<Integer> arr) {
    List<Integer> sorted = arr.stream().sorted().collect(Collectors.toList());
    BigInteger totalSum = BigInteger.valueOf(sorted.stream().mapToInt(Integer::intValue).sum());
    BigInteger minSum = totalSum.subtract(BigInteger.valueOf(sorted.get(sorted.size()-1)));
    BigInteger maxSum = totalSum.subtract(BigInteger.valueOf(sorted.get(0)));
    System.out.println(minSum + " "+maxSum);
}

Even then, it is resulting in negative values

Input : 793810624 895642170 685903712 623789054 468592370

Output : -1722871536 -1295821736

Why is it resulting in negative values even after using BigInteger, and how should it be handled?

Answer 1

The problem is that when you create totalSum, the overflow already happened as you summed the integers as int, which means the result is also an int. Only then does your code convert this overflowed result to a BigInteger.

Instead you need to do the calculation using BigInteger:

BigInteger totalSum = sorted.stream()
        .reduce(BigInteger.ZERO, 
                (sum, value) -> sum.add(BigInteger.valueOf(value)),
                BigInteger::add);

Which is equivalent to doing:

BigInteger totalSum = sorted.stream()
        .map(v -> BigInteger.valueOf(v.longValue()))
        .reduce(BigInteger.ZERO, BigInteger::add);

Answer 2

"... Why is it resulting in negative values even after using BigInteger, and how should it be handled? ..."

Utilize the map method to parse the stream as BigInteger values.
And, the reduce method to total the elements.

List<Integer> sorted = new ArrayList<>(arr);
Collections.sort(sorted);
BigInteger min
    = sorted.stream()
            .limit(sorted.size() - 1)
            .map(x -> new BigInteger(String.valueOf(x)))
            .reduce(BigInteger::add)
            .get();
BigInteger max
    = sorted.stream()
            .skip(1)
            .map(x -> new BigInteger(String.valueOf(x)))
            .reduce(BigInteger::add)
            .get();
System.out.println(min + " "+max);

Output

10 14

Answer 3

As said by others, converting the value to BigInteger after the data loss happened, will not solve your problem. The operation itself has to be performed using a larger data type than int.

But sorting the list, just to get minimum and maximum, also is very inefficient. There is a built-in operation, summaryStatistics(), which performs all necessary operations at once, getting mimimum, maximum, and the sum. It uses long for summing, which is sufficient to process all ordinary collections which can not have more than 2³¹ elements.

public static void miniMaxSum(List<Integer> arr) {
    IntSummaryStatistics s = arr.stream()
            .mapToInt(Integer::intValue).summaryStatistics();
    long totalSum = s.getSum();
    long minSum = totalSum - s.getMax();
    long maxSum = totalSum - s.getMin();
    System.out.println(minSum + " " + maxSum);
}

Note further that there is no reason to use boxed Integer or Long objects here.