Unexpected results working on Array of Integers

Question

While going through and re-factoring some Java code I wrote a while back for Project-Euler.

I ran into an issue with integer overflow where the answer was too large to contain in type int. This was straight-forward and intuitive but something caught me off-guard and I'm still unsure of. Was not only the type containing the large value needing its type changed to long but also the array of int's that I was finding the product for as well.

The premise for the problem goes like this:

Of this 1000 digit string find the greatest product of 13 adjacent digits.

We then take a long string (1000 digits) and parse it as integers to find the consecutive 13 digits with the greatest product.

My code:

import java.util.Arrays;


public class Euler_8
{
    private static String largeDigitStr = 
"73167176531330624919225119674426574742355349194934"+
"96983520312774506326239578318016984801869478851843"+
"85861560789112949495459501737958331952853208805511"+
"12540698747158523863050715693290963295227443043557"+
"66896648950445244523161731856403098711121722383113"+
"62229893423380308135336276614282806444486645238749"+
"30358907296290491560440772390713810515859307960866"+
"70172427121883998797908792274921901699720888093776"+
"65727333001053367881220235421809751254540594752243"+
"52584907711670556013604839586446706324415722155397"+
"53697817977846174064955149290862569321978468622482"+
"83972241375657056057490261407972968652414535100474"+
"82166370484403199890008895243450658541227588666881"+
"16427171479924442928230863465674813919123162824586"+
"17866458359124566529476545682848912883142607690042"+
"24219022671055626321111109370544217506941658960408"+
"07198403850962455444362981230987879927244284909188"+
"84580156166097919133875499200524063689912560717606"+
"05886116467109405077541002256983155200055935729725"+
"71636269561882670428252483600823257530420752963450";

    public static void main(String[] args)
    {
        long start = System.nanoTime();
        long greatestProduct = 0;

        for (int i = 0; i < largeDigitStr.length() - 12; i++) {
            String digitSubString = largeDigitStr.substring(i, i + 13);
            /* HERE is the line that caused the unexpected issue....
             * Now if I change this to .mapToLong and store it as long[]
             * No issues.... but the int[] will bring overflow
             * changing the line to:
             *   long[] digitArray = Arrays.stream(digitSubString.split("")
             *                             .mapToLong(Integer::parseInt)
             *                             .toArray();
             * (along with the digitProduct but that was obvious)
             * Fixes the overflow.
             */
            int[] digitArray = Arrays.stream(digitSubString.split(""))
                                      .mapToInt(Integer::parseInt)
                                      .toArray();
            long digitProduct = Arrays.stream(digitArray)
                                      .reduce(1, (x, y) -> x * y);
            if (digitProduct > greatestProduct) { 
                greatestProduct = digitProduct;
            }
        }
        long stop = System.nanoTime();
        System.out.println("Answer: " + greatestProduct);
        System.out.printf("Time: %.4f\n", ((float) stop - start) / 1_000_000_000);
    }
}

I would have expected the .map and .reduce to store the intermediary values in the variable digitProduct not the array members themselves. I'm almost positive now that since I had to change the type of the array that the .reduce is causing overflow as it calculates each successive term, or this off?

Answer 1

would have expected the .reduce to store the intermediary values in the variable digitProduct not the array members themselves.

.reduce does not store the intermediary values in digitProduct, but it doesn't store them in the "array members" either.

The problem is that Arrays.stream(digitArray) creates an IntStream, not a LongStream. There are multiple overloads of Array.stream (1, 2). The one that takes a int[] returns an IntStream and the one that takes a long[] returns a LongStream.

IntStream.reduce takes an IntBinaryOperator and LongStream.reduce takes a LongBinaryOperator.

The reason it overflow is that the return type of the lambda you pass is int. In .reduce(1, (x, y) -> x * y);, the lambda (x, y) -> x * y is expected to take two ints and return an int, and this is where * overflows. It has nothing to do with the array's type, or the type of the variable you are assigning the result to. It's simply because you are calling IntStream.reduce, which works with ints.

You don't need to create a long[]. You can convert the IntStream to a LongStream before calling reduce.

Arrays.stream(digitArray)
    .asLongStream()
    .reduce(1, (x, y) -> x * y);