# Solution to Problem 8 of 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 &lt; 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 &gt; 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. ### Posted by Kristian Jamil

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. Kristian

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 billy

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

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);``` billy

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 atul

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);

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;
}
```

[…] Solution to Problem 8 of Project Euler [MathBlog, 7th November […] Jean-Marie Hachey

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) Ilya

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 ``` Ilya

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 numbers = String.Join("", lines).ToCharArray()
findMaxProduct numbers 0 1 Ryan

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. Kristian

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

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

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); Rafi

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

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! Neha Arora

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! abhinav

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

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. A John S

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. Jay Prakash

@Neha Long will be able to hold the product of 13 digits. But I will suggest you to use BigInteger for larger numbers… David Wilson

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. John Varga

did they change this question since you answered? the problem asks for the product of 13 consecutive digits, not 5. merilynn

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.) why

cause problem needs the 13 digits adj numbers The Euler problem requires that you find the largest product of thirteen adjacent digits. This C# program produces the following output:

Solution is 5576689664895, whose product of digits is 23514624000; time: 2.000000000 ms.

Any string with zero in it will produce 0, so they can be skipped. Also, no need to ever multiply by 1.

private const string MS_FORMAT = “0.000000000”;
public void Problem8Solution()
{
Func<short[], ulong> FindProductOfDigits = (nums) =>
{
ulong result = 1;
for (int i = 0; i < nums.Length; i++)
{
if (nums[i] != 1) result *= (ulong)nums[i];
}
return result;
};

`const string numberStr = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";`

``` Stopwatch sw = Stopwatch.StartNew(); int len = numberStr.Length; ulong expected = 0L; string maxProductString = string.Empty; for (int i = 0; i <= len - 13; i++) { string subNum = numberStr.Substring(i, 13); int lastZeroIndex = subNum.LastIndexOf('0'); if (lastZeroIndex > -1) { i += (lastZeroIndex + 1); continue; } ulong product = FindProductOfDigits(subNum.ToCharArray().Select(n => short.Parse(n.ToString())).ToArray()); if (product > expected) { maxProductString = subNum; expected = product; } } var bruteMs = sw.ElapsedMilliseconds; ```

```testOutputHelper.WriteLine(\$"Solution is {maxProductString}, whose product of digits is {expected}; time: {bruteMs.ToString(MS_FORMAT)} ms"); ```

} Vishesh

@Bjarki Ágúst, your solution doesn’t work if we have to find 13 adjacent digits. Your solution gives an output: 2040733440. But the actual answer is: 23514624000. If possible, please enlighten me. Thank you.