Largest Product in a Series

The four adjacent digits in the 1000-digit number that have the greatest product are

\(9 × 9 × 8 × 9 = 5832\)

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Solution

The number might look daunting, but for any algorithm it’s small enough that we don’t need to optimize it much. This is the shortest solution (code-wise), but also the least efficient. We split the string into 13-element sliding windows, then calculate the product of the digits in each window.

Once we have the list of products, we simply take the maximum. Easy-peasy. Could you explain why this solution is inefficient and what could significantly improve it, even at the cost of no longer being functional?

object Euler008 extends EulerApp {
  override def execute(): Any = {
    val number = "73167176531330624919225119674426574742355349194934" +
      "96983520312774506326239578318016984801869478851843" +
      "85861560789112949495459501737958331952853208805511" +
      "12540698747158523863050715693290963295227443043557" +
      "66896648950445244523161731856403098711121722383113" +
      "62229893423380308135336276614282806444486645238749" +
      "30358907296290491560440772390713810515859307960866" +
      "70172427121883998797908792274921901699720888093776" +
      "65727333001053367881220235421809751254540594752243" +
      "52584907711670556013604839586446706324415722155397" +
      "53697817977846174064955149290862569321978468622482" +
      "83972241375657056057490261407972968652414535100474" +
      "82166370484403199890008895243450658541227588666881" +
      "16427171479924442928230863465674813919123162824586" +
      "17866458359124566529476545682848912883142607690042" +
      "24219022671055626321111109370544217506941658960408" +
      "07198403850962455444362981230987879927244284909188" +
      "84580156166097919133875499200524063689912560717606" +
      "05886116467109405077541002256983155200055935729725" +
      "71636269561882670428252483600823257530420752963450"

    number.sliding(13).map(_.map(_.asDigit.toLong).product).max
  }
}

Mutable solution

In the earlier approach, the sliding windows were completely independent of one another, which made it immutable, but as I’ve also mentioned – pretty inefficient.

By calculating the product of 13 elements, we were performing 11 redundant multiplications in each neighboring window.

Instead, we can maintain a running product — dividing by the digit that leaves the window and multiplying by the new digit that enters it. The only catch here are the zeroes that break the computation chain.

While this approach is definitely faster, it’s also more error-prone and harder to read. For example, consider the following line:

previous = buffer.remove(0).asDigit

It’s not immediately clear that remove(0) returns the element being removed. Moreover, if the .asDigit call were omitted, the code would still compile and run, but it would silently produce an incorrect result. For such a small task, the optimization is not worth the effort, so treat it merely as a mental exercise.