Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
}
share|improve this question
    
I see all those zeroes in the provided number and I think "that's where we should split the string." Instead of calculating for a 1000-digit number, calculate for a bunch of shorter numbers and then take the max. –  Snowbody Aug 8 at 20:21

2 Answers 2

up vote 4 down vote accepted

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 913 is comfortably smaller than 264 - 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 .

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.

share|improve this answer
    
@2000_success, initializing uint64_t with float was totally a careless mistake and you are right. Why while loop is not recognized by other programmers? Would you please elaborate a bit. I'm new with Circular buffer, but it seems a bit difficult to be readable than my approach. –  CroCo Aug 8 at 17:56
    
if (product > max) max = product; this is hard to be read. Isn't? Two lines are more readable than this. Any points regarding this ? –  CroCo Aug 8 at 17:59
    
Although they compile to the same code, the for-loop is more readable. The initialization, test, and update are all grouped together rather than scattered around. A well-written for-loop is therefore easy to understand at a glance. ("I know how this works! n is an index, going from the beginning of the string until the NUL terminator." — all from reading one line.) –  200_success Aug 8 at 18:01
    
I've written if (product > max) … both ways for your consideration. Either (a) put the statement on the same line and optionally omit braces, or (b) put the statement on a separate line with braces. Personally, I recommend (b), but I also included (a) for your consideration since you seemed to really like omitting braces. –  200_success Aug 8 at 18:06

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.

share|improve this answer
1  
The idea for the algorithm is good, but fails when there are 0's in the number. –  Yuushi Aug 8 at 6:21
    
Well, that issue could be fixed by checking for a divide by 0 and then proceeding to the next iteration if a 0 is found. This would add 986 conditionals, which is still 3k ops, vs nearly 13k for the original algorithm. Plus with the advanced branch prediction of modern cpu's, the cost of these conditionals will be virtually negligible. –  mleyfman Aug 8 at 6:29
    
I'm not saying it's much more expensive, I'm saying it's a bit more complicated. That won't quite work either, because at that point, your product will be 0, hence just skipping it and then performing the next iteration will still yield zero. Hence you need to check for a divide by zero and then recalculate the product from the DIGITNUM - 1 values following the zero. –  Yuushi Aug 8 at 6:36
1  
Yep, indeed. It can actually make things a bit faster - as soon as you hit a 0, you can jump forward by DIGITNUM values as you know all the products inbetween will be 0. It is a bit more finicky to get right, however. –  Yuushi Aug 8 at 7:01
1  
data[k++] = char2int(number[i-k]); - that's bad advice. k appears twice in that full expression, and is modified. That's a fast track to undefined behavior. –  Mat Aug 8 at 7:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.