Solution to Problem 8 of Project Euler

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

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

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

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!

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

Python <3
http://ideone.com/rn8DZK

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

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

isnt the answer 23514624000
cause problem needs the 13 digits adj numbers

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