Project Euler #8: Maximum product of 13 consecutive digits

Question

I've solved problem #8 in Project Euler, which asks to find the 13 consecutive digits with the greatest product from a particular 1000-digit number. I would like to hear any suggestions regarding my code. My solution is not restricted to 13 digits, and the user is allowed to choose any number of digits (as long as they are less than the given data).

// Link: http://projecteuler.net/problem=8

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

#define DIGITNUM 13

int char2int(const char n)
{
    return n - '0';
}

uint64_t getProduct(const int num[])
{
    uint64_t product = 1.0;
    int i;
    for (i = 0; i < DIGITNUM; ++i)
        product *= (uint64_t)num[i];

    return product;
}

int main()
{
    char number[] = "73167176531330624919225119674426574742355349194934"
                    "96983520312774506326239578318016984801869478851843"
                    "85861560789112949495459501737958331952853208805511"
                    "12540698747158523863050715693290963295227443043557"
                    "66896648950445244523161731856403098711121722383113"
                    "62229893423380308135336276614282806444486645238749"
                    "30358907296290491560440772390713810515859307960866"
                    "70172427121883998797908792274921901699720888093776"
                    "65727333001053367881220235421809751254540594752243"
                    "52584907711670556013604839586446706324415722155397"
                    "53697817977846174064955149290862569321978468622482"
                    "83972241375657056057490261407972968652414535100474"
                    "82166370484403199890008895243450658541227588666881"
                    "16427171479924442928230863465674813919123162824586"
                    "17866458359124566529476545682848912883142607690042"
                    "24219022671055626321111109370544217506941658960408"
                    "07198403850962455444362981230987879927244284909188"
                    "84580156166097919133875499200524063689912560717606"
                    "05886116467109405077541002256983155200055935729725"
                    "71636269561882670428252483600823257530420752963450";

    uint64_t product, max = 0.0;
    int data[DIGITNUM],
        i = DIGITNUM - 1; 

    while ( number[i] != '\0' )
    {
        int k = 0;
        while ( k < DIGITNUM  ){
           data[k] = char2int(number[i-k]);
           ++k;
        }

        product = getProduct(data);
        if ( product > max )
            max = product;

        ++i;
    }
    printf("The max product of %d digit is: %"PRId64" \n", DIGITNUM, max);

    return 0;
}

Answer 1

Data types

The number of consecutive digits you can support is limited not by the length of the input, but by the maximum value that can be stored in a uint64_t. While 9¹³ is comfortably smaller than 2⁶⁴ - 1, you should be cautious about overgeneralizing your claims.

It's weird that you initialize uint64_t integers with floating-point literals 1.0 and 0.0.

Loop and conditional style

Never omit the optional braces in conditional and loop blocks like that. By doing so, you are being a contributing factor to a future coding accident. If you want to omit the braces, then put the statement on the same line so that it cannot be misinterpreted. If you feel that braces take up too much vertical space, then please switch to the K&R brace style so that you don't feel compelled to omit them.

Your while-loops fit the classic for-loop pattern, and should be written as for-loops to make them easy for other programmers to recognize.

uint64_t max = 0;
int data[DIGITNUM];
for (int i = DIGITNUM - 1; number[i] != '\0'; ++i)
{
    for (int k = 0; k < DIGITNUM; ++k)
    {
        data[k] = char2int(number[i - k]);
    }

    uint64_t product = getProduct(data);
    if (product > max) max = product;
}

Algorithm

You transfer almost every digit to the temporary data array 13 times. It would be smarter to treat the data array as a circular-buffer.

uint64_t max = 0;
int consec[DIGITNUM];
for (int n = 0, c = 0; number[n] != '\0'; ++n, ++c) {
    if (c == DIGITNUM) {
        c = 0;        // Circular buffer wraparound
    }
    consec[c] = char2int(number[n]);
    if (n < DIGITNUM - 1) {
        continue;     // Circular buffer not fully initialized yet
    }

    uint64_t product = getProduct(consec);
    if (product > max) {
        max = product;
    }
}

Here, I've used n and c as array indices, which are mnemonics for the respective arrays number and consec that they index into.

Answer 2

Here's a few things I think could use improving:

Consistency

Maintain consistent spacing before and after expressions in parenthesis (like this) instead of alternating between style 1 (this style) and style 2 ( this style ). Same thing goes for spacing between chunks of code and for braces.

Styling

int data[DIGITNUM],
    i = DIGITNUM - 1;

That line(s) of code bothers me. An int[] and an int initialized with seemingly the same type (as that is what this type of initialization is for, like in the line previous to this one). This is all file and good for the compiler, but humans prefer more readable code.

Therefore, separate out those initializations onto an extra line.

Another nitpick is that you seem to only use the prefix version of incrementing (aka ++i). While I admire your consistency, I have mainly seen code written in the postfix fashion unless the algorithm necessitates the prefix version.

Algorithm

While this is a good start, it repeats a lot of multiplications. For every new number, it goes and does DIGITNUM multiplications. While this is still O(n), for larger DIGITNUM, it can get a bit slow. To fix this issue, divide by the first element and multiply by the new element. Below is an example:

Let's say I'm working with "123454321" and DIGITNUM = 3. The products could be calculated like so

prod = 1 * 2 * 3; // 6 = 1 * 2 * 3

prod = 6 * 4 / 1; // 24 = 2 * 3 * 4

prod = 24 * 5 / 2; // 60 = 3 * 4 * 5

prod = 60 * 4 / 3; // 80 = 4 * 5 * 4 (MAX)

prod = 80 * 3 / 4; // 60 = 5 * 4 * 3

prod = 60 * 2 / 5; // 24 = 4 * 3 * 2

prod = 24 * 1 / 4; // 6 = 3 * 2 * 1

So at each step, we multiply by the current element, then divide by the element that "falls off". In the case of DIGITNUM = 3, this yields no benefits, but as DIGITNUM grows, it grows increasingly useful in comparison to your approach.

For instance with DIGITNUM = 13 and 1000 characters (original parameters):

Your version does 13 * (1000 - 13) = 12831 multiplications

My version does 13 (initial) + ((1000 - 13) - 1) = 999 multiplications and 986 divisions

Assuming I don't have a gross arithmetic error somewhere, you can clearly see my way is going to be a lot faster.