8. Project Euler #8 : Largest product in a series.

Difficulty level is 5%.

This is a good problem that can be used at searching substring in a document.  In order to search a sub-string from a document, hashing can be used.  At this problem, product is needed, but, It is needed to check overflow and zero multiply.

13's single digit product can make 9's power 13, 2,541,865,828,329.  32bit integer can express about 4 billion, so I used 64bit integer type.

As problem's example, the number to be multiplied is 4.

For example, 10 series number 7316717653.

1st 7x3x1x6

2nd 3x1x6x7

3rd 1x6x7x1

...

We have to multiply 3 times at each number.  (10-3)x3 = 21.  We have to multiply 21 times.

Let's draw the multiplication.

7	3	1	6
	3	1	6	7
		1	6	7	1
			6	7	1	7
				7	1	7	6

There are 3 numbers duplicated multiply each time.  4 series product duplicate only 3.  But 13 series product make 12 duplicated multiplication.  

So I used first multiplication.

1st 7x3x1x6.

2nd (1st)x7/7

3rd (2nd)x1/3

...

Except first time, I used previous product, I can save 1 multiplication at each time.  When 13 series product, I can save 9 multiplication at each time.

In addition, there are zero values.  zero makes all production to zero.  So I use zero count variable, for counting zero's.  If zero count is not 0, I don't check maximum value.

My codes is below.  

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

typedef int64_t int64;

int main()
{
    char *s = "73167176531330624919225119674426574742355349194934"
        "96983520312774506326239578318016984801869478851843"
        "85861560789112949495459501737958331952853208805511"
        "12540698747158523863050715693290963295227443043557"
        "66896648950445244523161731856403098711121722383113"
        "62229893423380308135336276614282806444486645238749"
        "30358907296290491560440772390713810515859307960866"
        "70172427121883998797908792274921901699720888093776"
        "65727333001053367881220235421809751254540594752243"
        "52584907711670556013604839586446706324415722155397"
        "53697817977846174064955149290862569321978468622482"
        "83972241375657056057490261407972968652414535100474"
        "82166370484403199890008895243450658541227588666881"
        "16427171479924442928230863465674813919123162824586"
        "17866458359124566529476545682848912883142607690042"
        "24219022671055626321111109370544217506941658960408"
        "07198403850962455444362981230987879927244284909188"
        "84580156166097919133875499200524063689912560717606"
        "05886116467109405077541002256983155200055935729725"
        "71636269561882670428252483600823257530420752963450";
    char *h = s, *t = s;
    int64 max, c = 1, a, b, v = 0;

    for( int i = 0 ; i < 13 ; i++, t++ )
    {
        b = *t - '0';
        if( b != 0 ) c *= b;
        else v++;
    }
    if( v == 0 ) max = c;
    else max = 0;

    while( *t )
    {
        a = *h++ - '0';
        b = *t++ - '0';
        if( a != 0 ) c /= a; else v--;
        if( b != 0 ) c *= b; else v++;
        if( v == 0 && c > max ) max = c;
    }
    printf("Ans = %jd\n", max);
}

Pointer variable h is pointing the number to be erased, and pointer variable t is pointing the number to be added.   Variable max is saving current maximum product value, c is current phase product value, v saves how many zero's.