CODEWITHSUNDEEP
algorithm
Lernkurve
Lernkurve

Reputation: 21590

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

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

Upvotes: 5

Views: 1132

Answers (4)

Tomasz Nurkiewicz
Tomasz Nurkiewicz

Reputation: 341003

One optimization is to compute the product of the first five digits and in each iteration multiply by next digit and divide by the previous (moving window).

Another optimization is to immediately discard all digits around 0.

Upvotes: 2

Bill the Lizard
Bill the Lizard

Reputation: 406125

Yes and no. You do have to look at each sequence of five consecutive digits, but you don't have to multiply every one of those sequences each time through the loop. There are shortcuts you can take that will speed up processing. For example, if the next digit is a 0, you can skip ahead. Also, if the next digit is smaller than the last one you dropped from the sequence, you know the result of multiplying by the other four common digits will be smaller, so skip multiplying and go to the next digit. Tricks like this won't make much difference when you only have 1000 digits, but later problems will be the same, just with larger input.

Upvotes: 5

codaddict
codaddict

Reputation: 455440

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.

Upvotes: 7

tobias_k
tobias_k

Reputation: 82949

Since the question asks for consecutive digits, 'brute force' means O(n) in this case, n being the number of digits (1000). As long as there is not some sort of pattern in the number, you will need n steps for just scanning the number, so this is the fastest solution.

You can cache the product of the last 4 digits or do similar tricks, but you definitely won't get better than O(n).

Upvotes: 6

Related Questions