Project Euler Problem 8 Solution

Project Euler & HackerRank Problem 8 Solution

The largest product in a series
by {BetaProjects} | MAY 17, 2009 | 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 opening the file pe8.txt and concatenating its contents into one long string. Each line has all leading and trailing whitespace removed (e.g., \n, \t).

Next, each character is separated, converted to an integer digit, and then stored to a list named d.

d = [int(x) for x in ''.join(line.strip() for line in open('pe8.txt'))]

The variable L defines the search length and must be at least equal to the length of d. If not, we exit printing "None."

If there are enough digits then we consider all L–digit subsets and store their product. The for loop’s index, i, is the starting index for the next set inside the string and the reduce function multiplies each 13–digit subset together.

Finally, we capture the maximum product for all the sets.

L = 13
print ('Greatest product of', L, 'consecutive \ndigits =', end='') 
print "None."  if L>len(d) else  \
    max(reduce(mul, d[i:i+L]) for i in range(len(d)-L+1))

Easy mistakes 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

Further, many of these same programs would crash with an error or erroneously return zero when the search length exceeds the string length. It’s better to return some indication that an answer cannot be calculated, such as "None." Here’s an example for an undefined condition:
d = [0,0,0,1,9,2];
L = 13

HackerRank version

HackerRank 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

Last Word