Solution to Problem 8 of Project Euler

Written by on 7 November 2010

Topics: Project Euler

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.

19 Comments For This Post I'd Love to Hear Yours!

  1. Jamil says:

    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.

  2. Kristian says:

    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

  3. billy says:

    @Jamil will you post a version of your code using dynamic programming? I am interested to see how you do it

  4. Bjarki Ágúst says:

    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.

    // the number
    string p = "73167176531330624919225119674426574742355349194934"
    		   "96983520312774506326239578318016984801869478851843"
    		   "85861560789112949495459501737958331952853208805511"
    		   "12540698747158523863050715693290963295227443043557"
    		   "66896648950445244523161731856403098711121722383113"
    		   "62229893423380308135336276614282806444486645238749"
    		   "30358907296290491560440772390713810515859307960866"
    		   "70172427121883998797908792274921901699720888093776"
    		   "65727333001053367881220235421809751254540594752243"
    		   "52584907711670556013604839586446706324415722155397"
    		   "53697817977846174064955149290862569321978468622482"
    		   "83972241375657056057490261407972968652414535100474"
    		   "82166370484403199890008895243450658541227588666881"
    		   "16427171479924442928230863465674813919123162824586"
    		   "17866458359124566529476545682848912883142607690042"
    		   "24219022671055626321111109370544217506941658960408"
    		   "07198403850962455444362981230987879927244284909188"
    		   "84580156166097919133875499200524063689912560717606"
    		   "05886116467109405077541002256983155200055935729725"
    		   "71636269561882670428252483600823257530420752963450";
    
    int max = 1,        // the maximum product
    	prod = 1,       // the current product
    	len = size(p),  // the length of the number (1000 for this problem)
    	zeros = 0;      // number of zeros in the current product
    
    // loop through each digit of the number
    for (int i = 0; i < len; i++)
    {
    	// if there are 5 digits in our current product,
    	// we need to remove the oldest one to make room
    	// for the new digit
    	if (i + 1 > 5)
    	{
    		if (p[i - 5] == '0')
    		{
    			// if the old digit was a zero,
    			// we remove one zero from the current product
    			zeros--;
    		}
    		else
    		{
    			// if the old digit was not a zero,
    			// we divide it from the current product
    			prod = prod / (p[i - 5] - '0');
    		}
    	}
    
    	// now we add the new digit to the current product
    	if (p[i] == '0')
    	{
    		// if the current digit is a zero,
    		// we add one zero to the current product
    		zeros++;
    	}
    	else
    	{
    		// if the current digit is not a zero,
    		// we multiply our current product by the current digit
    		prod = prod * (p[i] - '0');
    	}
    
    	// if we have 5 digits in the current product
    	// and none of them are zero
    	if (i + 1 >= 5 && zeros == 0 && prod > max)
    	{
    		// then if the current product is larger than
    		// the largest product, we update the
    		// largest product
    		max = prod;
    	}
    }
    
    // print the maximum product
    printf("%d\n", max);
  5. billy says:

    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

  6. atul says:

    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.

    #include<stdio.h>
    #include<limits.h>
    int main()
    {
    
    int window=5;
    int prod_till_here=1,n;
    int i,max=INT_MIN,j=1,zero_flag=0;
    int input[]={1,2,3,4,5,0,5,6,7,8,9};
    n=sizeof(input)/sizeof(input[0]);
    
    for(i=0;i<n;i++,j++)
    {
    	prod_till_here*=input[i];   // keep on multiplying elements
    	
    	if(prod_till_here == 0)    // product can only be zero if currect multiplied element is zero , 
    	{			   // so fresh start the multiplication from next element onwards.	
    		prod_till_here=1;
    		zero_flag=1;       // present element has value muliplied is 0
    	}
    	if(prod_till_here > max && j==5) // updated max product
    	{
    		max=prod_till_here;
    	}
    	
    	if(j==5 || zero_flag==1)
    	{
    		if(!zero_flag)   // if j==5 and zero_flag==0 , then remove first element multiplied
    		{
    			prod_till_here=prod_till_here/input[i-(window-1)]; // window - 1 , because index start from 0
    			j=4;						   // next element will be part of previous 4 elements product.
    		}
    		else
    		{
    			j=0;       // if zero_flag==1 then skip current element as a part of next sub array product
                                       // by setting j=0 we are skipping this element 
    		       zero_flag=0; 
    		}
    	}
    
    }
    
    printf("\nMAX PRODUCT = %d",max);
    return 1;
    }
    
  7. Jean-Marie Hachey says:

    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)

  8. Ilya says:

    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

  9. Ilya says:

    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

  10. Ryan says:

    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.

  11. Kristian says:

    Ah yes, that makes sense. How you found any speed up when you use a char array instead?

  12. Aaron says:

    The correct solution is now 23514624000 since the problem has been updated to be the longest 13-digit number.

  13. Nitish Bhasin says:

    string number = &quot;7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450&quot;;
    int count = 0, checkProduct = 1, maxProduct = 1, digit = 5;
    while (count &lt; number.Length – digit)
    {
    int countDigit = 0;
    while (countDigit &lt; digit)
    {
    checkProduct *= Convert.ToInt32(number.Substring(count+countDigit, 1));
    countDigit++;
    }
    if (checkProduct &gt; maxProduct)
    maxProduct = checkProduct;
    count++;
    checkProduct = 1;
    }
    Console.WriteLine(&quot;Max Product: &quot;+maxProduct);

  14. Rafi says:

    I am new to programming, can someone explain how this code works step by step.

  15. Neha Arora says:

    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!

  16. Neha Arora says:

    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!

  17. abhinav says:

    the correct answer is 23514624000 .. u may check this..

  18. Dan Slotman says:

    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.

Trackbacks For This Post

  1. 8 : Largest product in a series | A Modern Prometheus

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.