Project Euler Problem 8 Solution

Project Euler Problem 8 Solution

The largest product in a series

by {BetaProjects} | Project Euler & HackerRank

Project Euler Problem 8 Statement

The four adjacent digits in the 1000–digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934699893520312774506326239578318016984…

Find the greatest product of 13 adjacent digits in the 1000–digit number.

Solution

We begin by reading the desired search length, K, and the string of digits. This string is then converted into a list of integers for easier processing.

d = list(map(int, input()))

Then we calculate the products of K-length contiguous subarrays from the list d and print the largest product found.

print(max(functools.reduce(operator.mul, d[i:i+K]) 
  for i in range(len(d)-K+1)))

An easy mistake to make

80% of the Python solutions listed in the Project Euler forum are wrong since they don’t consider the last digit in the search space. Because the solution to this problem lies somewhere in the middle, these programs calculate a correct response in this instance. However, if you were to run them with the following parameters they would fail by erroneously producing a zero instead of 18:
d = [0,0,0,1,9,2];
L = 3

HackerRank version

HackerRank logo

Solves all test cases for Hackerrank Project Euler Problem 8

HackerRank Project Euler 8 steps up the complexity by running up to 100 test cases and changing the search length from a fixed 13 digits to a variable 1 through 7 digits. The search object can range from 1 to 1000 digits.

Python Source Code

import functools, operator
for _ in range(int(input())):
    _, K = map(int, input().split())
    d = list(map(int, input()))
    print(max(functools.reduce(operator.mul, d[i:i+K])
        for i in range(len(d)-K+1)))

Last Word