After two easy problems, it's now time for Problem 8.
At first, this problem also seemed to me more complex than it really is. Let's have a look at the question:
Find the greatest product of five consecutive digits in the 1000-digit number.
So, basically what we need to do is:
- consider all chunks of this list of numbers that can be created by taking \(5\) consecutive digits from the beginning till the end (there will be \(n-5\) chunks if \(n\) is the number of digits in the list)
- for each chunk, multiply all the digits together (that's \(n-1\) products per chunk)
- pick the value corresponding to the greatest product.
At first I have considered resolving an easier problem first, like: find the chunk whose sum is bigger and then calculate that product. Assuming that sum is cheaper to calculate than product (and it is), we would have had \((n-5) \cdot (n-1)\) sums and just 1 product. However you can easily find examples where the sum of the digits is the same while the product is different: e.g. \(4 + 5 = 7 + 2 = 9\) but \(4 \cdot 5 = 20 > 7 \cdot 2 = 14\). Therefore that was a dead end.
A more mathematically sound approach to find the chunk giving the highest product might have been to first locate the chunk with the highest sum of logarithms of each digit and then calculate the corresponding product. However, a quick test revealed that logarithm is way slower than product.
Finally, a couple of micro-optimizations that occurred to me.
- You can skip all chunks containing at least one 0 (trivially, the product will be zero)
- You don't really have to multiply all the digits for each chunk (that is \((n-5) \cdot (n-1)\) products): once you have computed the product of the first chunk, the product of the next chunk would be the product of the previous chunk times the sixth digit divided by the first digit, and so on for subsequent chunks.
Eventually, I did not try to implement these two things, since brute force, which I am about to show you, is so quick that it's wasn't really worth it:
As you can see, we are generating a sequence of products and then pick the maximum value.
Each product is created by first taking a chunk of the array (using the
and then using
Array.fold to compute the product of all elements in the chunk.
Again, I have tried to keep the imperative part to a minimum and I was able to get by without using any mutable variable.