The biggest product in the series in python

Question

Four adjacent digits in the 1000-digit number that have the largest product:

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 largest product. What is the value of this product?

My solution to this problem:

 def no(x): previous=0 i=0 t=1 while i !=987: for num in x[i:i+13]: no=int(num) t=no*t if t>previous: previous = t i=i+1 t=1 return previous 

Are there any other good and effective ways to solve this problem? because I think mine is not very effective

Answer 1

You can use the generator expression in the max function and the correct key function, which calculates the product of your assignments. For this purpose you can use the map function to convert digits to an integer and reduce (in python 3.X functools.reduce ) to calculate the product of integers.

 >>> max((digits[i:i+13] for i in xrange(0, len(digits) - 12)), key=lambda x: reduce(mul, map(int, x))) '5576689664895' 

Note that if you have a new line symbol between your numbers, you need to delete them using the str.replace() method.

 digits = digits.replace('\n', '') 

More optimized approach:

Since you are dealing with 13 digits every time you can use the container to save your digits at each iteration, the best choice here would be deque() form collections module with maxlen=13 , which it pop and the exact operation is O (1) . Then you can calculate the product from the first 13 digits and each time you press and pop, your original product should be divided by the popped item and a few clicks on the item. and at each iteration you can just keep the sequence with the maximum product.

 from operator import mul from collections import deque from copy import copy def cal_max_prod(container, current_product): max_container = {'seq': copy(container), 'prod': current_product} for i in digits[13:]: popped_item = int(container.popleft()) container.append(i) try: push_item = int(i) current_product = (current_product / popped_item) * push_item except ZeroDivisionError: if '0' not in container: current_product = reduce(mul, map(int, container)) else: if current_product > max_container['prod']: max_container['prod'] = current_product max_container['seq'] = copy(container) return ''.join(max_container['seq']) 

Demo:

 container = deque(digits[:13], maxlen=13) current_product = reduce(mul, map(int, container)) print cal_max_prod(container, current_product) 5576689664895 

Answer 2

If you want to increase efficiency, you may notice that between the product of numbers from n to n + 12 and n + 1 to n + 13 you have 12 common factors.

So, pay attention to d _i n digits for i in [0, 999] and p _i products from m consecutive digits starting with d _i (m = 13 in your requirements):

• p _{i is} defined for i in [0, 1000th]
• p _{i + 1} = p _i / d _i * d _{i + m} when d _i ! = 0

At each iteration, you only make one product and one unit instead of 12 products, when d _i ! = 0, which should happen 9 times out of 10 for a random series

As always, optimize the algorithm before thinking about optimizing low-level code. But ... the code will be bigger or more complicated ...

Answer 3

For simplicity, instead of 13 digits, think of three digits. The first three digits:

 731 

Their product is 21. The following three digits:

 316 

The product is 18. We need an effective algorithm, so we have to answer one question: can we calculate the product of 731 from the product of 316 in constant time?

Answer: yes, if we look at the numbers to go from 731 to 316 , we delete 7 and add 6. But if we look at the product, we divide it by 7 and multiply by 6 Instead of calculating 7 × 3 × 1, then 3 × 1 × 6, then 1 × 6 × 7, etc. (Each time doing n multiplications), we can calculate the next product from the previous one (doing only 1 multiplication and 1 division).

This is a sketch for an efficient algorithm that runs in linear time:

 def maxproduct(number, digits): """Calculate the maximum product of the n-adjacent digits of number.""" zeros = 0 product = 1 result = 0 # Calculate the first, initial product. for x in number[:digits]: x = int(x) if x: product *= int(x) else: # This digit is 0. This will make our product zero # too (losing information about other digits) and will # also cause trouble with division later. Instead of # storing the zero in the product, we increment a counter. zeros += 1 if not zeros: # This product is the highest we have seen so far. result = product # Calculate the other products with the remaining digits. for i in range(digits, len(number)): # Digit to remove. x = int(number[i - digits]) # Digit to add. y = int(number[i]) if x: product //= x else: # The digit to remove is 0. zeros -= 1 if y: product *= y else: zeros += 1 if not zeros and product > result: result = product return result 

Answer 4

Using numpy if memory is not a problem. From the benchmarks on its numbers, the speed seems to be about 10 times faster than the OP code:

 import numpy as np def no2(x,d=13): k = len(x)-d t = np.ones(k,dtype=int) xa = np.fromiter(map(int,tuple(x)),dtype=int) for i in range(d): #xrange on python2.x t *= xa[i:k+i] return np.max(t) 

To get the numbers that return the maximum, replace np.max(t) with x[np.argmax(t):np.argmax(t)+d] . Example:

 no2('123456789101234123412351235324234324234') 1244160 

Benchmarking

When testing the string you specified, I find:

 #OP approach: %timeit -n 100 no(x) 100 loops, best of 3: 3.49 ms per loop #Kasramvd approach: %timeit -n 100 no3=max((s[i:i+13] for i in range(0, len(s) - 12)), key=lambda x: reduce(mul, map(int, x))) 100 loops, best of 3: 4.22 ms per loop #Andrea approach: %timeit -n 100 no4(x,13) 100 loops, best of 3: 777 µs per loop #numpy approach: %timeit -n 100 no2(x) 100 loops, best of 3: 315 µs per loop 

When there is a problem with memory and speed:

When benchmarking using a string 10 ^ 4 times longer (i.e. 10 ^ 7 digits):

 #numpy %timeit -n 10 no2(x5) 10 loops, best of 3: 2.2 s per loop #OP code %timeit -n 1 no(x5) 1 loop, best of 3: 37 s per loop #Andrea code %timeit -n 1 no4(x5,13) 1 loop, best of 3: 8.01 s per loop 

It is also about 10 times higher than the OP code. Therefore, if the array cannot fit in RAM (but the string can), then numpy will work better.

Answer 5

 data=list(" 73167176531330624919225119674426574742355349194934\ 96983520312774506326239578318016984801869478851843\ 85861560789112949495459501737958331952853208805511\ 12540698747158523863050715693290963295227443043557\ 66896648950445244523161731856403098711121722383113\ 62229893423380308135336276614282806444486645238749\ 30358907296290491560440772390713810515859307960866\ 70172427121883998797908792274921901699720888093776\ 65727333001053367881220235421809751254540594752243\ 52584907711670556013604839586446706324415722155397\ 53697817977846174064955149290862569321978468622482\ 83972241375657056057490261407972968652414535100474\ 82166370484403199890008895243450658541227588666881\ 16427171479924442928230863465674813919123162824586\ 17866458359124566529476545682848912883142607690042\ 24219022671055626321111109370544217506941658960408\ 07198403850962455444362981230987879927244284909188\ 84580156166097919133875499200524063689912560717606\ 05886116467109405077541002256983155200055935729725\ 71636269561882670428252483600823257530420752963450") print(len(data)) lst=list() while True: x=list(data[0:13]) pro=1 for i in x: pro*=int(i) lst.append(pro) data.pop(0) if len(data)==12: break print(max(lst)) print(len(data)) print(lst[0])