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.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

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

Idea

This problem can be treated as 'slide window' model.

From the beginning, slide the fixed-width window by one digit each time, compare the slided-in digit to the slided-out digit:

  • if in > out: this slide window is currently largest
  • else: we accumulate slided-in digits and get their product, so as slided-out digits
  • we can repeat above steps as long as currently largest window has intersection with new slide window
  • Otherwise, it is a new smaller problem, so can solve it recursively
In [1]:
from functools import reduce
In [2]:
series = """
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
"""
series = series.replace("\n", "")
In [3]:
def solve(series, width):
    
    # get product of `width` adjacent digits
    def product(series, start_index):
        assert start_index + width <= len(series)
        return reduce(lambda a, b: int(a) * int(b), series[start_index: start_index+width], 1)
    
    # get largest product in a series
    def get_largest(series):
        current_max = (product(series, 0), -1)
        
        out_window_product, in_window_product = 1, 1
        # slide window
        for window_index in range(len(series)-width):
            # new slide window has intersection with current max window
            if current_max[1] < window_index < current_max[1] + width:
                out_window_product *= int(series[window_index])
                in_window_product *= int(series[window_index+width])
                # the income digits of the new slide window has bigger product than outcome digits
                if out_window_product < in_window_product:
                    # replace with bigger product window
                    current_max = (current_max[0] // out_window_product * in_window_product, window_index)
                    out_window_product, in_window_product = 1, 1
            # new slide window is completely independent
            else:
                return max(current_max[0], get_largest(series[window_index+1:]))
        return current_max[0]
    
    # `0` makes no sense, so remove it and get split series that can contain `width` digits
    split_series = filter(lambda s: len(s) >= width, series.split('0'))
    return max(map(get_largest, split_series))
In [4]:
solve("1234579678", 2)
Out[4]:
63
In [5]:
solve(series, 4)
Out[5]:
5832
In [6]:
solve(series, 13)
Out[6]:
23514624000