Project Euler 8: Largest product in a series

Largest product in a series

Problem

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

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

Official Problem

Solution Approach

In this problem of the Largest product in a series, we have to find the thirteen adjacent numbers. The numbers should be chosen such that their product will be maximum. We have to choose thirteen digit number from a 1000 digit number provided. We have to only find the product now the actual numbers which constitute in giving the highest product value.

This problem can be easily tackled by the brute force method. We will iterate over all the numbers twice and keeping a window of 13 numbers to calculate the product. Since the product can become huge we have to use long or any other suitable data type for storage. At the end of every thirteen number window, we check if the intermediate product is the largest as of now or not. If it is we replace the product to have the largest value and the cycle repeats. Lastly, we return the maximum product as the answer.

Complexity

The time complexity of this approach is O(n2) as we are iterating through the numbers twice. The space complexity of this approach is constant or O(1) as we need just one variable to store the value of the maximum product and one to store the value of the running product.

Code Approach

Coming to the code part of Largest product in a series problem, we will initialize the maximum product variable. Then we have to run two loops where the outer loop will iterate over all the numbers which will be the starting point for the next loop in the calculation of the product. We also have to initialize the intermediate product variable before the start of the second loop. We calculate the product inside the second loop. After the second loop finishes, we compare the product variable value and maximum product variable value and store the maximum one. In the end, we need to return the maximum product as the answer.

Solution Code

Java Solution

Python Solution


For more Project Euler explained solutions visit Project Euler Detailed Solutions.

For Leetcode detailed solutions go to Leetcode Detailed Solutions.

If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page I will surely respond. Happy Coding 🙂

Leave a Comment

Your email address will not be published. Required fields are marked *