Project Euler #8: Is there a more efficient algorithm than brute force calculation?

Question

Question

Is there a better way to find the solution of the Project Euler problem 8, which is Find the greatest product of five consecutive digits in the 1000-digit number, than the brute force method.

I calculated all possible products and selected the greatest one -- brute force algorithm.

Is there a more efficient algorithm? Or is the brute force method the only way.

Side notes

• This is not a homework question.
• I am not asking for the result to problem 8.

Answer 1

You can use a sliding window of size 5 and solve this in O(d), where d is the number of digits in the input number.

You represent the window by index of the starting number in the window and the value of the window i is the product of elements with index [i, i+4]. Now in every iteration you slide the window to the right, effectively dropping the leftmost element and adding a new element to the right and the new value of the window is old_value / left_most_ele * new_right_ele. Keep doing this for every index i in range [0,d-5] and find the max window value.

Note that the brute force method of having nested loops where the inner loop runs five times is also a O(d) solution. But the above method is slightly better as we don't do five multiplications in each step but instead do one multiplication and one division.