Project Euler Problem #8: Largest product in a series

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450


Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

My solution: solve.h

#pragma once

int main(); //Is it correct to also declare the main method in the header file?
void doCalc(long long b, int pos);
extern int numbs[];
extern int arrPos;
extern long long highest;
extern long long current;


solve.cpp

#include "solve.h"
#include <iostream> // I was considering doing this in the header file

long long highest(0);
long long current(0);
int arrPos(0);
int numbs[] = {
7, 3, 1, 6, 7, 1, 7, 6, 5, 3, 1, 3, 3, 0, 6, 2, 4, 9, 1, 9, 2, 2, 5, 1, 1, 9, 6, 7, 4, 4, 2, 6, 5, 7, 4, 7, 4, 2, 3, 5, 5, 3, 4, 9, 1, 9, 4, 9, 3, 4,
9, 6, 9, 8, 3, 5, 2, 0, 3, 1, 2, 7, 7, 4, 5, 0, 6, 3, 2, 6, 2, 3, 9, 5, 7, 8, 3, 1, 8, 0, 1, 6, 9, 8, 4, 8, 0, 1, 8, 6, 9, 4, 7, 8, 8, 5, 1, 8, 4, 3,
8, 5, 8, 6, 1, 5, 6, 0, 7, 8, 9, 1, 1, 2, 9, 4, 9, 4, 9, 5, 4, 5, 9, 5, 0, 1, 7, 3, 7, 9, 5, 8, 3, 3, 1, 9, 5, 2, 8, 5, 3, 2, 0, 8, 8, 0, 5, 5, 1, 1,
1, 2, 5, 4, 0, 6, 9, 8, 7, 4, 7, 1, 5, 8, 5, 2, 3, 8, 6, 3, 0, 5, 0, 7, 1, 5, 6, 9, 3, 2, 9, 0, 9, 6, 3, 2, 9, 5, 2, 2, 7, 4, 4, 3, 0, 4, 3, 5, 5, 7,
6, 6, 8, 9, 6, 6, 4, 8, 9, 5, 0, 4, 4, 5, 2, 4, 4, 5, 2, 3, 1, 6, 1, 7, 3, 1, 8, 5, 6, 4, 0, 3, 0, 9, 8, 7, 1, 1, 1, 2, 1, 7, 2, 2, 3, 8, 3, 1, 1, 3,
6, 2, 2, 2, 9, 8, 9, 3, 4, 2, 3, 3, 8, 0, 3, 0, 8, 1, 3, 5, 3, 3, 6, 2, 7, 6, 6, 1, 4, 2, 8, 2, 8, 0, 6, 4, 4, 4, 4, 8, 6, 6, 4, 5, 2, 3, 8, 7, 4, 9,
3, 0, 3, 5, 8, 9, 0, 7, 2, 9, 6, 2, 9, 0, 4, 9, 1, 5, 6, 0, 4, 4, 0, 7, 7, 2, 3, 9, 0, 7, 1, 3, 8, 1, 0, 5, 1, 5, 8, 5, 9, 3, 0, 7, 9, 6, 0, 8, 6, 6,
7, 0, 1, 7, 2, 4, 2, 7, 1, 2, 1, 8, 8, 3, 9, 9, 8, 7, 9, 7, 9, 0, 8, 7, 9, 2, 2, 7, 4, 9, 2, 1, 9, 0, 1, 6, 9, 9, 7, 2, 0, 8, 8, 8, 0, 9, 3, 7, 7, 6,
6, 5, 7, 2, 7, 3, 3, 3, 0, 0, 1, 0, 5, 3, 3, 6, 7, 8, 8, 1, 2, 2, 0, 2, 3, 5, 4, 2, 1, 8, 0, 9, 7, 5, 1, 2, 5, 4, 5, 4, 0, 5, 9, 4, 7, 5, 2, 2, 4, 3,
5, 2, 5, 8, 4, 9, 0, 7, 7, 1, 1, 6, 7, 0, 5, 5, 6, 0, 1, 3, 6, 0, 4, 8, 3, 9, 5, 8, 6, 4, 4, 6, 7, 0, 6, 3, 2, 4, 4, 1, 5, 7, 2, 2, 1, 5, 5, 3, 9, 7,
5, 3, 6, 9, 7, 8, 1, 7, 9, 7, 7, 8, 4, 6, 1, 7, 4, 0, 6, 4, 9, 5, 5, 1, 4, 9, 2, 9, 0, 8, 6, 2, 5, 6, 9, 3, 2, 1, 9, 7, 8, 4, 6, 8, 6, 2, 2, 4, 8, 2,
8, 3, 9, 7, 2, 2, 4, 1, 3, 7, 5, 6, 5, 7, 0, 5, 6, 0, 5, 7, 4, 9, 0, 2, 6, 1, 4, 0, 7, 9, 7, 2, 9, 6, 8, 6, 5, 2, 4, 1, 4, 5, 3, 5, 1, 0, 0, 4, 7, 4,
8, 2, 1, 6, 6, 3, 7, 0, 4, 8, 4, 4, 0, 3, 1, 9, 9, 8, 9, 0, 0, 0, 8, 8, 9, 5, 2, 4, 3, 4, 5, 0, 6, 5, 8, 5, 4, 1, 2, 2, 7, 5, 8, 8, 6, 6, 6, 8, 8, 1,
1, 6, 4, 2, 7, 1, 7, 1, 4, 7, 9, 9, 2, 4, 4, 4, 2, 9, 2, 8, 2, 3, 0, 8, 6, 3, 4, 6, 5, 6, 7, 4, 8, 1, 3, 9, 1, 9, 1, 2, 3, 1, 6, 2, 8, 2, 4, 5, 8, 6,
1, 7, 8, 6, 6, 4, 5, 8, 3, 5, 9, 1, 2, 4, 5, 6, 6, 5, 2, 9, 4, 7, 6, 5, 4, 5, 6, 8, 2, 8, 4, 8, 9, 1, 2, 8, 8, 3, 1, 4, 2, 6, 0, 7, 6, 9, 0, 0, 4, 2,
2, 4, 2, 1, 9, 0, 2, 2, 6, 7, 1, 0, 5, 5, 6, 2, 6, 3, 2, 1, 1, 1, 1, 1, 0, 9, 3, 7, 0, 5, 4, 4, 2, 1, 7, 5, 0, 6, 9, 4, 1, 6, 5, 8, 9, 6, 0, 4, 0, 8,
0, 7, 1, 9, 8, 4, 0, 3, 8, 5, 0, 9, 6, 2, 4, 5, 5, 4, 4, 4, 3, 6, 2, 9, 8, 1, 2, 3, 0, 9, 8, 7, 8, 7, 9, 9, 2, 7, 2, 4, 4, 2, 8, 4, 9, 0, 9, 1, 8, 8,
8, 4, 5, 8, 0, 1, 5, 6, 1, 6, 6, 0, 9, 7, 9, 1, 9, 1, 3, 3, 8, 7, 5, 4, 9, 9, 2, 0, 0, 5, 2, 4, 0, 6, 3, 6, 8, 9, 9, 1, 2, 5, 6, 0, 7, 1, 7, 6, 0, 6,
0, 5, 8, 8, 6, 1, 1, 6, 4, 6, 7, 1, 0, 9, 4, 0, 5, 0, 7, 7, 5, 4, 1, 0, 0, 2, 2, 5, 6, 9, 8, 3, 1, 5, 5, 2, 0, 0, 0, 5, 5, 9, 3, 5, 7, 2, 9, 7, 2, 5,
7, 1, 6, 3, 6, 2, 6, 9, 5, 6, 1, 8, 8, 2, 6, 7, 0, 4, 2, 8, 2, 5, 2, 4, 8, 3, 6, 0, 0, 8, 2, 3, 2, 5, 7, 5, 3, 0, 4, 2, 0, 7, 5, 2, 9, 6, 3, 4, 5, 0};

void doCalc(long long b, int pos) {
current = numbs[pos];
for (int c = pos + 1; c <= pos + 12; c++){
current *= numbs[c];
}
if (current > highest)
highest = current;
if (arrPos <= ((sizeof(numbs)/sizeof(numbs[0])) - 13))
arrPos++;
if (arrPos < ((sizeof(numbs)/sizeof(numbs[0])) - 12))
doCalc(highest, arrPos);
}

int main() {
doCalc(highest, arrPos);
std::cout << "Greatest product: " << highest << std::endl;
return 0;
}

• @Incomputable Can't believe I missed this. Alright I fixed it. For some reason the code still worked despite there not being a return. – Tony J Jul 27 '17 at 4:38
• blame inlining :) and in general in C++ if the problem is not caught at compile time, all bets are off. Unless OS kernel detects something fishy, the program is free to do whatever it wants in case of undefined behavior. – Incomputable Jul 27 '17 at 4:39
• please do not update the code, since it invalidates other answers. I recommend waiting a day or two, collecting all of the reviews, and then asking follow-up question if you want to. See What should I do when someone answers my question? – Incomputable Jul 27 '17 at 5:12

Use container where appropriate

Right now, you have numbs defined as an array. If you, instead, defined it as an std::array or std::vector, it would make your life quite a bit easier (e.g., you wouldn't have to compute its size as (sizeof(numbs)/sizeof(numbs[0]) because its size() member would tell you the number of elements directly.

Avoid magic numbers

Right now, you have (for a couple of examples) - 12 and - 13 used in the code, with no explanation of what those numbers mean. I'd rather have something like static const int num_digits = 13;, then use num_digits and num_digits -1.

Use of recursion

In this case, you seem to gain nothing and lose a fair amount of clarity by using recursion instead of a simple loop. If at all possible, I'd just use a loop instead.

Avoid Global variables

Right now you've defined highest, current and arrPos as global variables, even though they're really only needed by one function. It's generally preferable to define variables at the smallest scope that's still sufficient for them to do their job.

Use parameters and return values

Hand in hand with avoiding globals is using parameters return values to pass values into a function, and get a result out of a function. This makes it much easier to (among other things) re-use that functionality elsewhere. It also makes a function much more self-contained so you can test it and have confidence in its working correctly (which often borders in impossible for code that uses a lot of globals).

A header is used primarily to share declarations (especially of classes and functions) between files, so code in one file can use those classes and functions contained in the other.

In this case, you are't sharing anything between implementation files (because you only have one), so using a header doesn't make sense.

Use Meaningful Names

doCalc (for only one example) is pretty meaningless. Nearly every function you ever write will do some sort of calculation. I'd prefer to call it something like largestProduct, so somebody reading the code has at least some chance of deducing what sort of calculation it does.

Formatting

I'd avoid using as wide of lines as you have in you definition of numbs. For many people, this will flow off the right side of the screen, requiring horizontal scrolling to see everything. I realize there's nothing very interesting there, but until you look, you don't know that for sure.

Summary

Based on these, one possible way to solve the problem would be something like this (I've skipped re-formatting numbs, simply because it's too much work, and I'm lazy).

#include <iostream>
#include <algorithm>
#include <vector>

template <class It>
long long compute_product(It start, size_t len) {
long long product = 1;
for (int i = 0; i < len; i++)
product *= *start++;
return product;
}

long long largest_product(std::vector<int> const &in, int digits) {
size_t max_pos = in.size() - digits + 1;

long long largest = 0;

for (int i = 0; i < max_pos; i++) {
long long product = compute_product(&in[i], digits);
largest = std::max(largest, product);
}
return largest;
}

int main() {

std::vector<int> numbs = {
7, 3, 1, 6, 7, 1, 7, 6, 5, 3, 1, 3, 3, 0, 6, 2, 4, 9, 1, 9, 2, 2, 5, 1, 1, 9, 6, 7, 4, 4, 2, 6, 5, 7, 4, 7, 4, 2, 3, 5, 5, 3, 4, 9, 1, 9, 4, 9, 3, 4,
9, 6, 9, 8, 3, 5, 2, 0, 3, 1, 2, 7, 7, 4, 5, 0, 6, 3, 2, 6, 2, 3, 9, 5, 7, 8, 3, 1, 8, 0, 1, 6, 9, 8, 4, 8, 0, 1, 8, 6, 9, 4, 7, 8, 8, 5, 1, 8, 4, 3,
8, 5, 8, 6, 1, 5, 6, 0, 7, 8, 9, 1, 1, 2, 9, 4, 9, 4, 9, 5, 4, 5, 9, 5, 0, 1, 7, 3, 7, 9, 5, 8, 3, 3, 1, 9, 5, 2, 8, 5, 3, 2, 0, 8, 8, 0, 5, 5, 1, 1,
1, 2, 5, 4, 0, 6, 9, 8, 7, 4, 7, 1, 5, 8, 5, 2, 3, 8, 6, 3, 0, 5, 0, 7, 1, 5, 6, 9, 3, 2, 9, 0, 9, 6, 3, 2, 9, 5, 2, 2, 7, 4, 4, 3, 0, 4, 3, 5, 5, 7,
6, 6, 8, 9, 6, 6, 4, 8, 9, 5, 0, 4, 4, 5, 2, 4, 4, 5, 2, 3, 1, 6, 1, 7, 3, 1, 8, 5, 6, 4, 0, 3, 0, 9, 8, 7, 1, 1, 1, 2, 1, 7, 2, 2, 3, 8, 3, 1, 1, 3,
6, 2, 2, 2, 9, 8, 9, 3, 4, 2, 3, 3, 8, 0, 3, 0, 8, 1, 3, 5, 3, 3, 6, 2, 7, 6, 6, 1, 4, 2, 8, 2, 8, 0, 6, 4, 4, 4, 4, 8, 6, 6, 4, 5, 2, 3, 8, 7, 4, 9,
3, 0, 3, 5, 8, 9, 0, 7, 2, 9, 6, 2, 9, 0, 4, 9, 1, 5, 6, 0, 4, 4, 0, 7, 7, 2, 3, 9, 0, 7, 1, 3, 8, 1, 0, 5, 1, 5, 8, 5, 9, 3, 0, 7, 9, 6, 0, 8, 6, 6,
7, 0, 1, 7, 2, 4, 2, 7, 1, 2, 1, 8, 8, 3, 9, 9, 8, 7, 9, 7, 9, 0, 8, 7, 9, 2, 2, 7, 4, 9, 2, 1, 9, 0, 1, 6, 9, 9, 7, 2, 0, 8, 8, 8, 0, 9, 3, 7, 7, 6,
6, 5, 7, 2, 7, 3, 3, 3, 0, 0, 1, 0, 5, 3, 3, 6, 7, 8, 8, 1, 2, 2, 0, 2, 3, 5, 4, 2, 1, 8, 0, 9, 7, 5, 1, 2, 5, 4, 5, 4, 0, 5, 9, 4, 7, 5, 2, 2, 4, 3,
5, 2, 5, 8, 4, 9, 0, 7, 7, 1, 1, 6, 7, 0, 5, 5, 6, 0, 1, 3, 6, 0, 4, 8, 3, 9, 5, 8, 6, 4, 4, 6, 7, 0, 6, 3, 2, 4, 4, 1, 5, 7, 2, 2, 1, 5, 5, 3, 9, 7,
5, 3, 6, 9, 7, 8, 1, 7, 9, 7, 7, 8, 4, 6, 1, 7, 4, 0, 6, 4, 9, 5, 5, 1, 4, 9, 2, 9, 0, 8, 6, 2, 5, 6, 9, 3, 2, 1, 9, 7, 8, 4, 6, 8, 6, 2, 2, 4, 8, 2,
8, 3, 9, 7, 2, 2, 4, 1, 3, 7, 5, 6, 5, 7, 0, 5, 6, 0, 5, 7, 4, 9, 0, 2, 6, 1, 4, 0, 7, 9, 7, 2, 9, 6, 8, 6, 5, 2, 4, 1, 4, 5, 3, 5, 1, 0, 0, 4, 7, 4,
8, 2, 1, 6, 6, 3, 7, 0, 4, 8, 4, 4, 0, 3, 1, 9, 9, 8, 9, 0, 0, 0, 8, 8, 9, 5, 2, 4, 3, 4, 5, 0, 6, 5, 8, 5, 4, 1, 2, 2, 7, 5, 8, 8, 6, 6, 6, 8, 8, 1,
1, 6, 4, 2, 7, 1, 7, 1, 4, 7, 9, 9, 2, 4, 4, 4, 2, 9, 2, 8, 2, 3, 0, 8, 6, 3, 4, 6, 5, 6, 7, 4, 8, 1, 3, 9, 1, 9, 1, 2, 3, 1, 6, 2, 8, 2, 4, 5, 8, 6,
1, 7, 8, 6, 6, 4, 5, 8, 3, 5, 9, 1, 2, 4, 5, 6, 6, 5, 2, 9, 4, 7, 6, 5, 4, 5, 6, 8, 2, 8, 4, 8, 9, 1, 2, 8, 8, 3, 1, 4, 2, 6, 0, 7, 6, 9, 0, 0, 4, 2,
2, 4, 2, 1, 9, 0, 2, 2, 6, 7, 1, 0, 5, 5, 6, 2, 6, 3, 2, 1, 1, 1, 1, 1, 0, 9, 3, 7, 0, 5, 4, 4, 2, 1, 7, 5, 0, 6, 9, 4, 1, 6, 5, 8, 9, 6, 0, 4, 0, 8,
0, 7, 1, 9, 8, 4, 0, 3, 8, 5, 0, 9, 6, 2, 4, 5, 5, 4, 4, 4, 3, 6, 2, 9, 8, 1, 2, 3, 0, 9, 8, 7, 8, 7, 9, 9, 2, 7, 2, 4, 4, 2, 8, 4, 9, 0, 9, 1, 8, 8,
8, 4, 5, 8, 0, 1, 5, 6, 1, 6, 6, 0, 9, 7, 9, 1, 9, 1, 3, 3, 8, 7, 5, 4, 9, 9, 2, 0, 0, 5, 2, 4, 0, 6, 3, 6, 8, 9, 9, 1, 2, 5, 6, 0, 7, 1, 7, 6, 0, 6,
0, 5, 8, 8, 6, 1, 1, 6, 4, 6, 7, 1, 0, 9, 4, 0, 5, 0, 7, 7, 5, 4, 1, 0, 0, 2, 2, 5, 6, 9, 8, 3, 1, 5, 5, 2, 0, 0, 0, 5, 5, 9, 3, 5, 7, 2, 9, 7, 2, 5,
7, 1, 6, 3, 6, 2, 6, 9, 5, 6, 1, 8, 8, 2, 6, 7, 0, 4, 2, 8, 2, 5, 2, 4, 8, 3, 6, 0, 0, 8, 2, 3, 2, 5, 7, 5, 3, 0, 4, 2, 0, 7, 5, 2, 9, 6, 3, 4, 5, 0
};

static const int digits = 13;

auto largest = largest_product(numbs, digits);

std::cout << "The largest product is: " << largest << "\n";
}

• I'll be honest the reason I used recursion was because I thought the code was taking too long to execute and recursion would make it run faster. That wasn't the problem in reality, it was that the code ran infinitely and I just didn't know. – Tony J Jul 27 '17 at 5:55
• @TonyJ: Compilers try to optimize recursion into a loop whenever possible, to remove the overhead of actually making a function call and running the function's setup code. Also, args + return values optimize much better than globals. Even after inlining, the compiler might have to make sure all the values in memory for globals are "consistent" with the source code as written every time you call an external function. Compilers can do a better job inlining "pure" functions that only look at their args. – Peter Cordes Jul 27 '17 at 8:25
• @PeterCordes: Do you actually have any evidence for optimisation of recursive functions? Using recursion that can be turned into loops has always been exceedingly rare in C or C++, and with iterators becoming more and more fashionable, they will become rarer. – gnasher729 Jul 27 '17 at 18:58
• Your code fails if the array ends in 13 nines. You don't calculate the product of the last 13 numbers. – gnasher729 Jul 27 '17 at 19:02
• @gnasher729: Oops--quite right. Corrected, with my thanks. – Jerry Coffin Jul 27 '17 at 19:19

In addition to the post by Jerry Coffin:

I'd recommend that instead of initializing numbs within the file, the data should be stored within some file and then be read. There should be CSV readers available, but writing one might also be a nice exercise.

Also, the algorithm you use can be improved. Currently it works like

maximum = 0
for i = 0 .. n-13-1
current = product of numbs[i] .. numbs[i+13]
maximum = max(maximum, current)


Assuming that division is not far more slow than multiplication, I'd propose

current = product numbs[0] .. numbs[13]
maximum = current;
for i = 14 .. n-1
current /= numbs[i-14]
current *= numbs[i]
maximum = max(maximum, current)


This requires only a multiplication and a division where you would do 12 multiplications before. Not changing the complexity class, though.

One would need to extend this algorithm to make a jump and a recomputation whenever a zero is found, but I wanted to keep my pseudo code simple. Shouldn't be that hard to add this.

Another thing, I'm usually in favor for classes and would make the whole thing something like AdjacentProductSolver. Although the task is a procedural one and I don't mind that much about it being solved with functions. Jerry Coffin made it into a templated utility function, which is good if you think that this is to be used in the future on all kind of different things, but I'd assume that this is a solver of a very specific problem in a very small context and thus should be kept specific and isolated.

• Actually changing to use the division does change the complexity, from O(N * M) to just O(N). I considered the possibility, but unless you really expected the number of items to increase from 13 to something substantially larger, I doubt it's going to be much of a win (though I'll admit, I didn't benchmark to check). – Jerry Coffin Jul 27 '17 at 16:51
• Division will run into problems because the array contains zeroes. – gnasher729 Jul 27 '17 at 18:48
• @JerryCoffin: Fun fact: the throughput of 12 independent multiplies (1 per clock) is better than the latency of 1 multiply + 1 division (3 + ~26 cycles), on modern mainstream x86 CPUs (those numbers from Intel Haswell/Skylake). However, since zeros are special, if they're common then to optimize for performance you should worry about how your code is scanning for runs of 13 non-zero numbers. (See this comment.) – Peter Cordes Jul 28 '17 at 6:04
• By being even a little bit clever about the multiplies, you can reuse a lot of the work for multiple windows. (e.g. the product of 4 adjacent digits is reused in 13-4 = 9 windows.) – Peter Cordes Jul 28 '17 at 6:08
• @gnasher729 I addressed that. See the second paragraph below the pseudo code. As soon as a zero is detected, one jumps after the zero in position and then starts the basic algorithm again. Does not increase the amount of operations (reduces them if the zero is found in an initial product) – Aziuth Jul 28 '17 at 8:55

If we look at the method definition

void doCalc(long long b, int pos)


we see a method parameter long long b which isn't used anywhere in that method. You should either remove it or better use it. There is no need to use a class wide variable if a method scoped one is there.

Omitting braces {} although they are optional is dangerous because it can lead to hidden and therefore hard to track bugs.

I guess (don't know c++ so correct me if I am wrong) that the sizeof(numbs) and sizeof(numbs[0]) always returns the same value, so storing the value in a constant should speed this up a little bit (unless the compiler optimize it anyway).

• sizeof() is a compile-time operator. (sizeof(numbs)/sizeof(numbs[0]) will reliably optimize away to a constant. It's kinda clunky to write it out multiple times as part of another expression, though. (Related: a C++11 countof() implementation that won't bite you with pointers instead of arrays: g-truc.net/post-0708.html) – Peter Cordes Jul 27 '17 at 8:53