Problem 8: 1000 digit number

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

Sol:

The method adopted to solve the problem was creating a window of 5 digits, finding the product of numbers in it and then sliding the window over the whole of the number. Each time we advance one digit, a new digit is included in the window which is multiplied to earlier product and an old digit is discarded by which the product is divided. Thus we get a new product each time we slide the window. Finding maximum of the products is the answer. 

This algorithm is simple, but trouble arises when there is a zero in between the number at some place. For those cases. in which zeroes appear, the 5 digit combinations are discarded i.e. they are not allowed to interfere with the window product. Thus awkward values are avoided.

The coding part is 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()

{

    int n,i,p=1,max,j;

    FILE *fp=fopen("input.txt","r");

    fscanf(fp,"%d\n",&n);

    char *a=(char*)malloc(n * sizeof(char));

    a[0]='\0';

    char temp[100];

    while(fscanf(fp,"%s",temp)!=EOF)

    {

                    strcat(a,temp);

    }

    int x=0;

    for(i=0;i<5;i++)

    {

                    if((a[x+i]-'0')==0)

                    {

                                 p=1;

                                 x=x+i+1;

                                 i=-1;

                    }

                    else

                        p=p * (a[x+i]-'0');

    }

    max=p;

    int st=x+i;

    for(i=st;i<n;i++)

    {

                    if((a[i]-'0')==0)

                    {

                               p=1;

                               x=i+1;

                               for(j=0;(j<5)&&((x+j) < n);j++)

                               {

                                   if((a[x+j]-'0')==0)

                       {

                                 p=1;

                                 x=x+j+1;

                                 j=-1;

                       }

                       else

                         p=p * (a[x+j]-'0');

                               

                               }

                               i=x+j-1;                

                    }

                    else

                    {

                               p=p/(a[i-5]-'0');

                               p=p*(a[i]-'0');

                    }

                    if(max

                             max=p;

    }

    printf("\n%d\n",max);

}

In the program the input is taken from file input.txt, n denotes the number of digits in the number, the character array 'a' is used to store the number. p denotes the product in the current window and max denotes the maximum product obtained yet.

As it can be seen, when zero occurs, the new product is obtained by finding a nearest window which doesn't have zero.

Please post your comments and doubts...
Suggestion for better algorithms are always welcome.....