Problem 8: Largest Product in a Series

View on Project Euler

Project Euler Problem 8 Solution

EulerSolve provides an optimized solution for Project Euler Problem 8, Largest Product in a Series, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The input is the fixed 1000-digit decimal string from the problem statement. For a chosen window length \(w\), the task is to find the largest product of \(w\) consecutive digits. In the original Euler instance, \(w = 13\). Mathematically, we are evaluating a function \(M(w)\) on one fixed digit sequence. The implementations also define sensible boundary behavior: if \(w \le 0\) or \(w\) is longer than the string itself, the returned value is \(0\). Mathematical Approach Let the digits be \(d_0, d_1, \dots, d_{m-1}\), where each \(d_i \in \{0,1,\dots,9\}\) and \(m=1000\) for the Euler input. Window Products Form the Entire Search Space For every valid starting position \(i\), define the window product $$P_i=\prod_{t=0}^{w-1} d_{i+t}, \qquad 0 \le i \le m-w.$$ The desired value is therefore $$M(w)=\max_{0 \le i \le m-w} P_i.$$ This formula already explains why a complete scan is correct: every block of \(w\) consecutive digits appears exactly once as one of these windows, so taking the maximum over all valid starts cannot miss the optimum. Zeros Split the Search into Independent Runs Because all digits are nonnegative, a zero destroys the whole product of any window that touches it....

Detailed mathematical approach

Problem Summary

The input is the fixed 1000-digit decimal string from the problem statement. For a chosen window length \(w\), the task is to find the largest product of \(w\) consecutive digits. In the original Euler instance, \(w = 13\).

Mathematically, we are evaluating a function \(M(w)\) on one fixed digit sequence. The implementations also define sensible boundary behavior: if \(w \le 0\) or \(w\) is longer than the string itself, the returned value is \(0\).

Mathematical Approach

Let the digits be \(d_0, d_1, \dots, d_{m-1}\), where each \(d_i \in \{0,1,\dots,9\}\) and \(m=1000\) for the Euler input.

Window Products Form the Entire Search Space

For every valid starting position \(i\), define the window product

$$P_i=\prod_{t=0}^{w-1} d_{i+t}, \qquad 0 \le i \le m-w.$$

The desired value is therefore

$$M(w)=\max_{0 \le i \le m-w} P_i.$$

This formula already explains why a complete scan is correct: every block of \(w\) consecutive digits appears exactly once as one of these windows, so taking the maximum over all valid starts cannot miss the optimum.

Zeros Split the Search into Independent Runs

Because all digits are nonnegative, a zero destroys the whole product of any window that touches it. If the string is decomposed into maximal zero-free runs \(R_1,\dots,R_s\), and a typical run is written as \(R_j=(e_0,e_1,\dots,e_{r_j-1})\), then every window either lies completely inside one run or has product \(0\).

That lets us rewrite the problem as

$$M(w)=\max\left(0,\max_j M_j(w)\right), \qquad M_j(w)=\max_{0 \le i \le r_j-w}\prod_{t=0}^{w-1} e_{i+t},$$

where a run contributes only when \(r_j \ge w\). This is the key structural fact of Problem 8: zeros do not merely lower a candidate product, they partition the whole search into independent nonzero segments plus the fallback value \(0\).

Consecutive Windows on a Zero-Free Run

Inside a run with no zeros, consecutive window products satisfy an exact recurrence. If

$$P_i=\prod_{t=0}^{w-1} e_{i+t},$$

then for \(0 \le i < r_j-w\),

$$P_{i+1}=P_i \cdot \frac{e_{i+w}}{e_i}.$$

This identity is valid precisely because \(e_i \neq 0\). It is the natural mathematical basis for a rolling-product or sliding-window optimization. The provided implementations do not use this recurrence; they recompute each \(P_i\) from scratch. That choice keeps the code simple and avoids special zero bookkeeping, which is perfectly reasonable for a 1000-digit input.

Worked Examples from the Verified Checks

For the short sequence \(123456789\) with \(w=2\), the window products are

$$2, 6, 12, 20, 30, 42, 56, 72,$$

so the maximum is \(72\), attained by the final window \(89\).

For the 1000-digit Euler string with \(w=4\), one verified optimal block is \(9989\), giving

$$9 \times 9 \times 8 \times 9 = 5832.$$

For the original target \(w=13\), the maximizing block is \(5576689664895\), and its product is

$$5 \times 5 \times 7 \times 6 \times 6 \times 8 \times 9 \times 6 \times 6 \times 4 \times 8 \times 9 \times 5 = 23514624000.$$

Why Direct Multiplication Is Enough Here

The largest possible product of 13 decimal digits is \(9^{13}=2541865828329\), well below the range of signed 64-bit integers. So there is no overflow problem for the Euler parameter.

There are exactly \(1000-13+1=988\) candidate windows, and the straightforward method performs \(13\) digit multiplications per window. That is only

$$988 \times 13 = 12844$$

digit multiplications, plus trivial loop overhead. For such a small fixed workload, the simpler \(O(mw)\) scan is mathematically transparent and practically fast.

How the Code Works

Input Representation and Boundary Cases

The C++, Python, and Java implementations store the 1000-digit number as one immutable string literal. They all accept a window length parameter, and they all return \(0\) immediately when the requested window is nonpositive or longer than the digit string.

Exhaustive Window Scan

The implementation then loops over every legal starting position \(i\). For each start, it initializes a product accumulator to \(1\), multiplies the \(w\) digits in positions \(i,i+1,\dots,i+w-1\), and compares that product with the best value seen so far.

In other words, the outer loop enumerates the windows from the formula for \(M(w)\), and the inner loop reconstructs the invariant “the accumulator equals the product of the current window” from scratch each time.

Cross-Language Consistency

All three versions implement the same mathematics. The C++ and Java versions use 64-bit integer arithmetic; Python integers are arbitrary precision, so the same computation is still exact. The code also includes the same two checkpoints in every language: the toy case \((123456789, 2) \mapsto 72\), and the 1000-digit check with \(w=4\) giving \(5832\).

Complexity Analysis

For a digit string of length \(m\), there are \(m-w+1\) windows, and each one is recomputed using \(w\) multiplications. The running time is therefore

$$O((m-w+1)w)=O(mw).$$

The memory usage is \(O(1)\) beyond the stored digit string and a few scalar variables.

For the Euler input with \(m=1000\) and \(w=13\), this means 988 window evaluations and 12,844 digit multiplications. A rolling-product implementation on zero-free runs could reduce the time to \(O(m)\), but the current exhaustive scan is already more than sufficient.

Footnotes and References

  1. Problem page: Project Euler - Problem 8
  2. Product in mathematics: Wikipedia - Product (mathematics)
  3. Zero and its algebraic role: Wikipedia - Zero (mathematics)
  4. Sliding-window technique: GeeksforGeeks - Window Sliding Technique
  5. Asymptotic complexity notation: Wikipedia - Big O notation

Problem 8 source code

C++

#include <cstdint>
#include <iostream>
#include <string>

namespace {

using u64 = std::uint64_t;

constexpr const char* DIGITS =
    "73167176531330624919225119674426574742355349194934"
    "96983520312774506326239578318016984801869478851843"
    "85861560789112949495459501737958331952853208805511"
    "12540698747158523863050715693290963295227443043557"
    "66896648950445244523161731856403098711121722383113"
    "62229893423380308135336276614282806444486645238749"
    "30358907296290491560440772390713810515859307960866"
    "70172427121883998797908792274921901699720888093776"
    "65727333001053367881220235421809751254540594752243"
    "52584907711670556013604839586446706324415722155397"
    "53697817977846174064955149290862569321978468622482"
    "83972241375657056057490261407972968652414535100474"
    "82166370484403199890008895243450658541227588666881"
    "16427171479924442928230863465674813919123162824586"
    "17866458359124566529476545682848912883142607690042"
    "24219022671055626321111109370544217506941658960408"
    "07198403850962455444362981230987879927244284909188"
    "84580156166097919133875499200524063689912560717606"
    "05886116467109405077541002256983155200055935729725"
    "71636269561882670428252483600823257530420752963450";

struct Options {
    int window = 13;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (const char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }

    value = parsed;
    return true;
}

bool parse_arguments(const int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--window=", options.window)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.window > 0;
}

u64 max_adjacent_product(const std::string& digits, const int window) {
    if (window <= 0 || static_cast<std::size_t>(window) > digits.size()) {
        return 0ULL;
    }

    u64 best = 0ULL;
    for (std::size_t i = 0; i + static_cast<std::size_t>(window) <= digits.size(); ++i) {
        u64 prod = 1ULL;
        for (int j = 0; j < window; ++j) {
            const char ch = digits[i + static_cast<std::size_t>(j)];
            prod *= static_cast<u64>(ch - '0');
        }
        if (prod > best) {
            best = prod;
        }
    }

    return best;
}

u64 solve(const int window) {
    return max_adjacent_product(DIGITS, window);
}

bool run_checkpoints() {
    if (max_adjacent_product("123456789", 2) != 72ULL) {
        std::cerr << "Checkpoint failed for custom digits" << '\n';
        return false;
    }
    if (solve(4) != 5832ULL) {
        std::cerr << "Checkpoint failed for window=4" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }

    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.window) << '\n';
    return 0;
}

Python

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

def max_adjacent_product(digits, window):
    if window <= 0 or window > len(digits):
        return 0
    best = 0
    for i in range(len(digits) - window + 1):
        prod = 1
        for j in range(window):
            prod *= int(digits[i + j])
        if prod > best:
            best = prod
    return best

def solve(window=13):
    return max_adjacent_product(DIGITS, window)

if __name__ == "__main__":
    assert max_adjacent_product("123456789", 2) == 72, "Checkpoint failed for custom digits"
    assert solve(4) == 5832, "Checkpoint failed for window=4"
    print(solve())

Java

public class Euler8 {
    static final String DIGITS = "73167176531330624919225119674426574742355349194934"
            + "96983520312774506326239578318016984801869478851843"
            + "85861560789112949495459501737958331952853208805511"
            + "12540698747158523863050715693290963295227443043557"
            + "66896648950445244523161731856403098711121722383113"
            + "62229893423380308135336276614282806444486645238749"
            + "30358907296290491560440772390713810515859307960866"
            + "70172427121883998797908792274921901699720888093776"
            + "65727333001053367881220235421809751254540594752243"
            + "52584907711670556013604839586446706324415722155397"
            + "53697817977846174064955149290862569321978468622482"
            + "83972241375657056057490261407972968652414535100474"
            + "82166370484403199890008895243450658541227588666881"
            + "16427171479924442928230863465674813919123162824586"
            + "17866458359124566529476545682848912883142607690042"
            + "24219022671055626321111109370544217506941658960408"
            + "07198403850962455444362981230987879927244284909188"
            + "84580156166097919133875499200524063689912560717606"
            + "05886116467109405077541002256983155200055935729725"
            + "71636269561882670428252483600823257530420752963450";

    static long maxAdjacentProduct(String digits, int window) {
        if (window <= 0 || window > digits.length())
            return 0;
        long best = 0;
        for (int i = 0; i + window <= digits.length(); i++) {
            long prod = 1;
            for (int j = 0; j < window; j++) {
                prod *= digits.charAt(i + j) - '0';
            }
            if (prod > best)
                best = prod;
        }
        return best;
    }

    static long solve(int window) {
        return maxAdjacentProduct(DIGITS, window);
    }

    public static void main(String[] args) {
        assert maxAdjacentProduct("123456789", 2) == 72 : "Checkpoint 1 failed";
        assert solve(4) == 5832 : "Checkpoint 2 failed";
        System.out.println(solve(13));
    }
}