Project Euler: Problem 8

Problem 8

Approach - Sliding Window

It's not obvious to me that there's a more clever way to solve this than to just use a sliding window.

We'll iterate through each of the 13-adjacent-digits and take the largest one.

There are some small optimizations we could make though:

• Skip the multiplication step for any series of digit that includes a '$0$' (multiplication by $0$ always results in $0$).

• When calculating the product for the next set of digits, we don't need to multiply all 13 numbers from scratch. Instead, we can divide the previous product by the first digit in its window, and multiply the result by the last digit in the next window.

For example, imagine we have a 9 digit number, 123,456,789 and want to find the largest product of any 4 adjacent numbers.

The product of the first window is $1 \cdot 2 \cdot 3 \cdot 4 = 24$.

The product of the next 4 digit number would be $\frac {24}{1} \cdot 5 = 120$.

And the next 4 digit product would be $\frac {120}{2} \cdot 6 = 360$

For 13 numbers, this means just 2 additional mathematical operations are needed to calculate the product of the next sliding window, instead of 12.

We'll also convert the long number to an array, with each digit being one element in the array. This will make iterating the number more straightforward, and will avoid repetitive string/int conversions.

JS Solution

Conclusion

This one's basically a leetcode problem. You can easily achieve time complexity of O(n^2) with a nested for loop. But the better solution is the sliding window technique for O(n) time complexity.

The forums have some interesting solutions. But my favorite was someone who used LabVIEW to solve this.

Also

I learned that converting a long digit number to a string in Javascript is not as simple as calling $String(longNumber)$. Javascript internally converts the number to it's exponential form, so the stringified version looks something like $\text{\textquoteleft}1.23e45\text{\textquoteright}$.

Final answer

$23514624000$