1
\$\begingroup\$

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?

This is my solution to the problem above.

> def largest_product_series(n, series):
>     series = str(series)
>     largest = 0
>     for i in range(0,1000-n):
>         temp = np.prod([int(series[j]) for j in range(i,n+i)])
>         largest = max(temp, largest)
>     return largest

I am having a hard time figuring out what is wrong with my code. It works just fine with n = 4. But somehow it didn't output the correct answer when n = 13.

Here's the link to the problem. Euler 8

\$\endgroup\$
3
  • 5
    \$\begingroup\$ Since that's a bug, shouldn't this question go on stackoverflow? Anyway, consider that the product of 13 digits could be larger than 2 billion \$\endgroup\$
    – harold
    Jan 14, 2021 at 2:50
  • 1
    \$\begingroup\$ Are you sure it doesn’t work? It gives the number 23514624000 which I’m reading is the correct answer. \$\endgroup\$ Jan 14, 2021 at 3:31
  • 1
    \$\begingroup\$ Is the solution passing the tests on the website? \$\endgroup\$
    – pacmaninbw
    Jan 14, 2021 at 13:37

1 Answer 1

2
\$\begingroup\$

I think your current code is working- it seems like it’s getting the same answer as other people who say they solved it (i.e. 23514624000). So I think it belongs here.

Right now, if you wanted to use this for any string of digits and any length of consecutive numbers, it would be \$O(n^2)\$ time complexity because you would have to multiply at most (length-of-series / 2) * (length-of-series / 2) numbers. Something you could use to fix that is a deque from the collections module. You could use it to know what to divide and what to multiply to get the current product, and you could also use it to track how many zeros are in the current sequence of consecutive numbers. If you do this then you only need to multiply or divide at most (length-of-series * 2) - 1 numbers, so it’s \$O(n)\$.

import collections

def find_max_prod(n, series):
    
    if len(series) < n:
        return 0
        
    current_nums = collections.deque(maxlen=n)
    zero_count = 0
    max_prod = 1
    my_iter = iter(series)
    
    for _ in range(n):
        next_n = int(next(my_iter))
        max_prod *= next_n
        current_nums.append(next_n)
        if next_n == 0:
            zero_count += 1

    current_prod = max_prod if max_prod > 0 else 1
    
    for str_n in my_iter:
        n_out = current_nums.popleft()
        n_in = int(str_n)
        current_nums.append(n_in)
        if n_in == 0:
            zero_count += 1
        if n_out == 0:
            zero_count -= 1
        else:
            current_prod //= n_out
        if n_in != 0:
            current_prod *= n_in
            if current_prod > max_prod and zero_count == 0:
                max_prod = current_prod
    
    return max_prod

or with Toby Speight‘s suggestion:

import collections

def max_of_substr(n, substr):
    current_nums = collections.deque(maxlen=n)
    my_iter = iter(substr)
    max_prod = 1
    
    for _ in range(n):
        next_n = int(next(my_iter))
        max_prod *= next_n
        current_nums.append(next_n)
    
    current_prod = max_prod

    for str_n in my_iter:
        n_out = current_nums.popleft()
        n_in = int(str_n)
        current_nums.append(n_in)
        current_prod //= n_out
        current_prod *= n_in
        if current_prod > max_prod:
            max_prod = current_prod
    
    return max_prod

def find_max_prod(n, series):
    max_substr_generator = (
        max_of_substr(n, substr)
        for substr in series.split('0')
        if len(substr) >= n
        )
    return max(max_substr_generator, default=0)
\$\endgroup\$
1
  • 2
    \$\begingroup\$ You can avoid counting zeros if instead you split the string on every 0 (and discard too-short substrings). Then just test each of those substrings in turn. \$\endgroup\$ Jan 14, 2021 at 14:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.