patterncMinor
Project Euler #8: Maximum product of 13 consecutive digits
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
It's weird that you initialize
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.
Algorithm
You transfer almost every digit to the temporary
Here, I've used
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.