We have now treated a couple of problems where a really clever solution could be derived from different branches of number theory. Problem 8 of Project Euler is inherently different. The problem goes
Find the greatest product of five consecutive digits in the 1000-digit number.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
I have been given it many deep thoughts, but I haven’t been able to find any other way than a brute force approach. We need to run through all the numbers, to find the largest product.
The only real question we have to answer in this problem is how to store the data we have to search through. We certainly can’t store the number in a numeric variable like an int or a long, it is far too big for that. On the other hand we don’t need to interpret the number as a whole. We need to interpret it as consecutive integers. In my solution I have chose to represent the input number as a string, and then converting them on the fly.
Over at Basildon Coder he has chosen to represent the input as an list of integers, that means he will not have to convert them when doing the calculation.
The logic in the solution is really basic. As you can see below the solution, is a loop through the sequence of numbers, calculating the product and checking if it is larger than the previously largest found.
const String p = "73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450"; int largest = 0; int numm = 0; for (int i = 0; i < p.Length-4; i++) { numm = int.Parse(p.Substring(i, 1)) * int.Parse(p.Substring(i+1, 1)) * int.Parse(p.Substring(i+2, 1)) * int.Parse(p.Substring(i+3, 1)) * int.Parse(p.Substring(i+4, 1)); if (numm > largest) { largest = numm; } }
That was fairly simple piece of code, and the result is
The largest product is 40824 Solution took 0 ms
Closing remarks
As we have seen this solution is more than fast enough. I tried to pursue another solution where I use a sliding calculation, such that I for each iteration multiply by one number, and divide by the number which is no longer part of the product. However, that required me to check for zero division and so on. So I decided to stick with only this solution.
Like the last few problems, I have made the source code available for you to download.
You can also use a form of dynamic programming to keep track of the value of the product of the last 4 digits of the previous product since they will be used in the next calculation. This can save lots of time in calculation since you already have 3 of the 4 multiplication that you will need to accomplish before hand.
Hi Jamil
You are absolutely right. However, I do think the majority of the time is spend parsing the string, so if you just keep track of the parsed values, I think you saved the most operations.
However, it was really easy to solve, so I saw no reason to actually keep optimizing the code.
For bigger problems you are right though.
/Kristian
@Jamil will you post a version of your code using dynamic programming? I am interested to see how you do it
Hi Billy.
Here is an implementation of a dynamic programming solution to this problem. The only thing we have to take special care of are the zeros, but other than that it should be easy to understand.
Bjarki Ágúst,
Thank you for your fast response and also for your helpful comments in the code. It really helped me understand what you did. 🙂
-Billy
Here is another solving using DP approch …idea is if current element is 0 then fresh start from next element.
by resetting prod_till_here=1.
[…] Solution to Problem 8 of Project Euler [MathBlog, 7th November […]
Table 1
Consecutive digits and greatest products in the 1000-digit number (Project Euler – Problem 8)
http://img11.hostingpics.net/pics/387861pe8tableone.jpg
Based on prime factorization, it seems that the algo doesnt apply for the following lengths (i.e. prime factors with more than one digit) in the consecutive digit lengths: 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 28, 29, 36, 37 and 40.
[Table 1 : In red : prime factors containing more than one digit].
___
Table 2
Sequences with 5 to 10 consecutive digits and greatest products in the 1000-digit number (Project Euler – Problem 8)
http://img11.hostingpics.net/pics/124393PE8tabletwo.jpg
In the column “Consecutive digits List”, the digits are presented in their original order and are then sorted. Permutations of those numbers are frequent in the original 1000-digit number.
Hence, the first number 78 999 in Table 2 appears as 99879 in the original 1000-digit number.
Maybe I am missing something in the application of the algo…
___
Sources:
1): Project Euler Problem 8
Kristian’s algorithm
http://www.mathblog.dk/files/euler/Problem8.cs
2): Prime Factorization Calculator
http://www.mathblog.dk/tools/prime-factorization/
3) Microsoft Visual C# 2010 Express
4) Microsoft Office Excel (2007)
Here is the F# version very similar to your. Just in case you are curious. The only improvement, is that the length of consecutive digits is specified in a field.
let productLength = 5
let rec findMaxProduct (numbers:char[]) startNumber product =
if startNumber>= numbers.Length - productLength then product
else
let newProduct = numbers |> Seq.skip startNumber
|> Seq.take productLength
|> Seq.map (fun x -> Int32.Parse(x.ToString()))
|> Seq.fold(fun prod elem -> prod * elem) 1
findMaxProduct numbers (startNumber + 1) (List.max([newProduct; product]))
let lines = File.ReadAllLines("Problem8.txt")
let numbers = String.Join("", lines).ToCharArray()
findMaxProduct numbers 0 1
Here is the F# version very similar to your. Just in case you are curious. The only improvement, is that the length of consecutive digits is specified in a field. (Sorry for wrong code tag, kindly as you to remove previous post)
let productLength = 5
let rec findMaxProduct (numbers:char[]) startNumber product =
if startNumber>= numbers.Length – productLength then product
else
let newProduct = numbers |> Seq.skip startNumber
|> Seq.take productLength
|> Seq.map (fun x -> Int32.Parse(x.ToString()))
|> Seq.fold(fun prod elem -> prod * elem) 1
findMaxProduct numbers (startNumber + 1) (List.max([newProduct; product]))
let lines = File.ReadAllLines("Problem8.txt")
let numbers = String.Join("", lines).ToCharArray()
findMaxProduct numbers 0 1
You can take advantage of ASCII codes instead of using int.Parse()
var number = “…..”; // big number
var ints = number.ToCharArray().Select(c => c – ‘0’).ToArray();
I used a sliding window approach and skipped ahead 5 windows anytime I detected the last digit was 0. It cuts out about 40% of the possible products.
Ah yes, that makes sense. How you found any speed up when you use a char array instead?
The correct solution is now 23514624000 since the problem has been updated to be the longest 13-digit number.
string number = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
int count = 0, checkProduct = 1, maxProduct = 1, digit = 5;
while (count < number.Length – digit)
{
int countDigit = 0;
while (countDigit < digit)
{
checkProduct *= Convert.ToInt32(number.Substring(count+countDigit, 1));
countDigit++;
}
if (checkProduct > maxProduct)
maxProduct = checkProduct;
count++;
checkProduct = 1;
}
Console.WriteLine("Max Product: "+maxProduct);
I am new to programming, can someone explain how this code works step by step.
Hello,
In Project Euler, Problem 8, the solution required is for 13 adjacent digits but your solution only shows it for 5 places. In case of 13 adjacent digits, I doubt if numm will be able to hold the product. Please let me know what to do in that case. Thanks!
Hello,
Your solution shows product numm for 5 adjacent places but Problem 8 of Project Euler asks for product of 13 adjacent places and I doubt, in this case, if numm will be able to hold the product of 13 digits. So can you suggest what should be done here? Thanks in advance!
the correct answer is 23514624000 .. u may check this..
The answer is 23,514,624,000. As you can see, that’s about 10 times bigger than the maximum value for a signed integer (2,147,483,647).
In Java you can use a long. In C-family languages you can use a unsigned 32-bit integer. In C# you could use a BigInteger.
Python <3
http://ideone.com/rn8DZK
Suggestion: Add Logs instead of multiplying digits.
Column 1 – the 1000 digits
Column 2 – The log of the digit in column 1, except -100 for zeroes (No further checking for zeroes needed). Set up a table or array to provide the logs rather than repeatedly recalculating the logs of the nine digits.
Add the first five logs. Subsequently add the log of the next digit and subtract the log of the outgoing digit.
Antilog the largest sum.
@Neha Long will be able to hold the product of 13 digits. But I will suggest you to use BigInteger for larger numbers…
Since multiplication by 0 is always zero. You can split the string by 0 to get substrings that don’t contain zero. discard those that don’t have length >= 13 and then use the sliding multiplication trick.
did they change this question since you answered? the problem asks for the product of 13 consecutive digits, not 5.
The “0” split and dynamically recalculating product while passing throug the sequenced String was my very best idea; I just got angry when my original Euler result turned out to be correct (thanks to this discussion) and I still could not pass some test cases for Euler 8 at hackerrank. (I forgot to compare product of first k digits to max, just compared the later dynamic product, oops.)