HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

Project Euler #8: Maximum product of 13 consecutive digits

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
maximumdigitsproductprojecteulerconsecutive

Problem

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 
#include 

#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  max )
            max = product;

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

    return 0;
}

Solution

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

Code Snippets

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

Context

StackExchange Code Review Q#59465, answer score: 6

Revisions (0)

No revisions yet.