· Development

Project Euler 8: The Largest Product of 13 Adjacent Digits with a Zero-Counting Sliding Window

Largest product of 13 adjacent digits via a sliding window that tracks the zero count and nonzero-digit product separately. Why it never divides by zero, why 64-bit is needed, in C++17 and Python 3.

Project Euleralgorithmssliding window

Spoiler warning · This post walks through the full solution and states the answer. To try it yourself first, start with Project Euler Problem 8.

This is the eighth problem in the Project Euler series. Multiplying 13 digits for every window already gets you the answer quickly. This post goes a step further and builds a sliding window that, on each step, divides out the digit that leaves and multiplies in the digit that enters. The obstacle is zero. We show that counting zeros instead of multiplying by them means we never divide by zero, and we work out why the product does not fit in 32 bits.

Spoiler warning: this post contains a full solution and the answer. If you want to try it yourself first, start with the original problem. Posts in this series never carry ads, because the problem text is licensed under CC BY-NC-SA 4.0, which is non-commercial.

Problem

The original problem gives a single 1000-digit number. As an example, it shows that the largest product of four adjacent digits in that number is 9 × 9 × 8 × 9 = 5832. The task is to find the largest product of thirteen adjacent digits in the same number.

There is no input. The number is on the original problem page and is copied verbatim into the code in this post. In this post n (= 1000) is the number of digits, k (= 13) is the window length, and dᵢ is the i-th digit from the left (counting from 0). There are n − k + 1 = 988 windows of length k. The output is a single integer.

Background

Sliding windows. When a window of length k moves one step at a time from the left end to the right end, each step changes only one digit leaving on the left and one digit entering on the right. If the values we keep for the window can be updated from those two digits alone, there is no need to recompute each window from scratch.

A product with a zero in it is zero. If a window contains even one zero, its product is 0. And you cannot divide by 0. So the idea of “dividing out the digit that leaves” does not work as is when that digit is 0 (step 2 of the derivation).

Exact division. If an integer a can be written a = d × b with d ≠ 0, then a / d is exactly b with no remainder. Even though integer division (C++ /, Python //) rounds down, in this case there is nothing to round away. The solution only ever divides in this form.

From characters to digits. The number is stored as a string. The character codes of '0' through '9' increase by one at each step, so the value of a digit character c is c − '0'. Before computing the answer, the programs check that the string really consists of 1000 characters from '0' to '9'.

Fixed-width integers. The largest value an unsigned 32-bit integer can hold is 2³² − 1 = 4294967295; for 64 bits it is 2⁶⁴ − 1 = 18446744073709551615. Going past that silently wraps the value around and gives a wrong answer. Which of the two a product of 13 digits fits in is worked out under Complexity.

Brute force

For each starting position, multiply the k digits from scratch and keep the largest product.

best = 0
for start in range(n - k + 1):
    product = 1
    for j in range(start, start + k):
        product *= d[j]
    best = max(best, product)

This is correct, and with (n − k + 1) × k = 988 × 13 = 12844 multiplications it is plenty fast for this problem. The cost is O(nk): the longer the window, the more work each window takes, in proportion to k. Yet two neighbouring windows share k − 1 digits, so the same multiplications are repeated almost k times over. Below we cut the work per window to a constant. The brute force is not thrown away: the implementations use it as a cross-check.

Derivation

Step 1: check the problem’s example by hand. The four adjacent digits 9, 9, 8, 9 highlighted in the original problem multiply to 9 × 9 = 81, 81 × 8 = 648, 648 × 9 = 5832, which matches the example. Whether those four digits really form the largest window cannot be checked by hand, so the programs compute k = 4 and confirm that 5832 comes out.

We also pick a small example to trace the algorithm by hand. For the digit string 3021945 and k = 3 there are five windows.

3 0 2 → 0
0 2 1 → 0
2 1 9 → 18
1 9 4 → 36
9 4 5 → 180
largest: 180

Step 2: sliding by dividing and multiplying, and its trap. If we know the window’s product P, it seems that one step with the leaving digit dₒᵤₜ and the entering digit dᵢₙ gives the new product as P / dₒᵤₜ × dᵢₙ. Without zeros that is right. But in the example above the first window 3 0 2 has product 0, and the moment that 0 leaves the window we would need “0 / 0”. Once the product becomes 0, the information about what had been multiplied into it is gone.

Step 3: count zeros instead of multiplying by them. Keep two values for the window:

  • Z: the number of zeros in the window
  • P: the product of the nonzero digits in the window (1 if there are none)

Then the window’s product is 0 if Z > 0 and P if Z = 0. On each step:

  • If the leaving digit is 0, decrease Z by 1; otherwise divide P by that digit.
  • If the entering digit is 0, increase Z by 1; otherwise multiply P by that digit.

Why we never divide by zero, and why the division is exact. We divide only when the leaving digit d is nonzero. And P is the product of the nonzero digits in the window, d included, so P = d × (product of the other nonzero digits), and P / d is exactly that other product with no remainder. A zero is never multiplied into P, so P is always at least 1, and while zeros remain in the window P still means exactly “the product of the nonzero digits”. The situation “dividing while a zero remains” never arises: zeros only move in and out through Z.

Step 4: remove first, then add. On each step we remove the leaving digit first and add the entering digit afterwards. Then at no moment are more than k digits multiplied into P, so P ≤ 9ᵏ. In the other order, k + 1 digits are briefly multiplied in and the bound grows to 9ᵏ⁺¹ (see integer bounds under Complexity).

Here is the trace for 3021945, k = 3. i is the position of the entering digit; from i ≥ 3 on, dᵢ₋₃ is removed first.

i=0: 3 enters            Z=0, P=3   (window not yet full)
i=1: 0 enters            Z=1, P=3
i=2: 2 enters            Z=1, P=6   window 302 → Z>0 so 0, best=0
i=3: 3 leaves, 1 enters  Z=1, P=2   window 021 → 0
i=4: 0 leaves, 9 enters  Z=0, P=18  window 219 → 18, best=18
i=5: 2 leaves, 4 enters  Z=0, P=36  window 194 → 36, best=36
i=6: 1 leaves, 5 enters  Z=0, P=180 window 945 → 180, best=180

This matches multiplying each window directly in step 1. At i = 3, dividing P = 6 by 3 gives exactly 6 / 3 = 2; at i = 4, when the 0 leaves, there is no division, only Z goes down.

Final algorithm

  1. Start with Z = 0, P = 1, best = 0.
  2. For i = 0 to n − 1:
    • If i ≥ k, remove dᵢ₋ₖ (if 0, Z − 1; otherwise P / dᵢ₋ₖ).
    • Add dᵢ (if 0, Z + 1; otherwise P × dᵢ).
    • If i + 1 ≥ k (the window is full), Z = 0 and P > best, set best = P.
  3. Return best. A window whose product is 0 equals best’s starting value 0, so it needs no separate comparison.

The precondition is 1 ≤ k ≤ n (see the boundary cases).

Correctness proof

Let W(i) = { dⱼ : max(0, i − k + 1) ≤ j ≤ i } be the window right after the i-th digit is processed. The following invariant holds: “Z is the number of zeros in W(i), and P is the product of the nonzero digits in W(i).”

  • Start. Before any digit is processed the window is empty, with Z = 0 and P = 1 (the empty product).
  • When i < k. We only add, and W(i) = W(i − 1) ∪ {dᵢ}, so updating Z or P by the adding rule keeps the invariant.
  • When i ≥ k. W(i) is W(i − 1) with dᵢ₋ₖ removed and dᵢ added. If dᵢ₋ₖ is 0, Z − 1 is right; if not, by the argument in step 3, P / dᵢ₋ₖ is exactly the product of the remaining nonzero digits. Adding dᵢ then works as in the previous case.
  • So for every i with i + 1 ≥ k, W(i) is exactly the k digits dᵢ₋ₖ₊₁ … dᵢ, and its product is 0 if Z > 0 and P otherwise. There are n − k + 1 such i, from k − 1 to n − 1, so every window is seen once. best is the largest of those products (0 if all are 0).

Complexity

  • Time. Each digit costs a few comparisons and at most one division and one multiplication, so the total is O(n), independent of the window length k. Compared with the brute force’s O(nk), a factor of k is gone.
  • Space. Apart from the digit string itself, only a few values such as Z, P and best: O(1).

Integer bounds.

  • P and best are products of at most k nonzero digits (step 4), so they are at most 9¹³ = 2541865828329 (about 2.54 × 10¹²). That is larger than the unsigned 32-bit maximum 4294967295, and since 2⁴¹ = 2199023255552 < 9¹³ < 2⁴² = 4398046511104 it needs 42 bits. So a 32-bit integer is not enough. Whether an actual window’s product exceeds 32 bits depends on the number, but we cannot know that in advance, so the type is chosen from the bound.
  • The C++ code uses unsigned long long. The C++ standard guarantees this type is at least 64 bits wide, so it holds 9¹³ with room to spare. The intermediate products of the brute-force cross-check are also products of at most k digits and stay under the same bound.
  • Python’s int has unlimited precision and cannot overflow.
  • Indices and Z are std::size_t and at most n = 1000. Z counts only zeros in the window, so it never goes below 0 (a removed zero is always one that was in the window).

C++17

#include <cstddef>
#include <iostream>
#include <string>

// The 1000-digit number from the problem, 50 digits per line.
const std::string DIGITS =
    "73167176531330624919225119674426574742355349194934"
    "96983520312774506326239578318016984801869478851843"
    "85861560789112949495459501737958331952853208805511"
    "12540698747158523863050715693290963295227443043557"
    "66896648950445244523161731856403098711121722383113"
    "62229893423380308135336276614282806444486645238749"
    "30358907296290491560440772390713810515859307960866"
    "70172427121883998797908792274921901699720888093776"
    "65727333001053367881220235421809751254540594752243"
    "52584907711670556013604839586446706324415722155397"
    "53697817977846174064955149290862569321978468622482"
    "83972241375657056057490261407972968652414535100474"
    "82166370484403199890008895243450658541227588666881"
    "16427171479924442928230863465674813919123162824586"
    "17866458359124566529476545682848912883142607690042"
    "24219022671055626321111109370544217506941658960408"
    "07198403850962455444362981230987879927244284909188"
    "84580156166097919133875499200524063689912560717606"
    "05886116467109405077541002256983155200055935729725"
    "71636269561882670428252483600823257530420752963450";

// The value of the digit at position i of a string of '0'..'9'.
unsigned long long digit_at(const std::string& digits, std::size_t i) {
    return static_cast<unsigned long long>(digits[i] - '0');
}

// Largest product of k adjacent digits, for 1 <= k <= digits.size().
// Rolling window: zeros counts the zeros in the window and nonzero_product is the
// product of its other digits, so the window's product is 0 if zeros > 0 and
// nonzero_product otherwise. Only nonzero digits are ever divided out.
unsigned long long largest_product(const std::string& digits, std::size_t k) {
    unsigned long long nonzero_product = 1;
    std::size_t zeros = 0;
    unsigned long long best = 0;
    for (std::size_t i = 0; i < digits.size(); ++i) {
        if (i >= k) {
            // Remove the digit leaving the window before adding the new one,
            // so the window never holds more than k digits.
            const unsigned long long outgoing = digit_at(digits, i - k);
            if (outgoing == 0) {
                --zeros;
            } else {
                nonzero_product /= outgoing;
            }
        }
        const unsigned long long incoming = digit_at(digits, i);
        if (incoming == 0) {
            ++zeros;
        } else {
            nonzero_product *= incoming;
        }
        if (i + 1 >= k && zeros == 0 && nonzero_product > best) {
            best = nonzero_product;
        }
    }
    return best;
}

// Multiplies every window from scratch. Used only to cross-check largest_product.
unsigned long long largest_product_brute(const std::string& digits, std::size_t k) {
    unsigned long long best = 0;
    for (std::size_t start = 0; start + k <= digits.size(); ++start) {
        unsigned long long product = 1;
        for (std::size_t j = start; j < start + k; ++j) {
            product *= digit_at(digits, j);
        }
        if (product > best) {
            best = product;
        }
    }
    return best;
}

int main() {
    if (DIGITS.size() != 1000) {
        return 1;
    }
    for (const char c : DIGITS) {
        if (c < '0' || c > '9') {
            return 1;
        }
    }
    if (largest_product("3021945", 3) != 180 || largest_product("1020304", 3) != 0) {
        return 1;
    }
    if (largest_product(DIGITS, 4) != 5832) {
        return 1;
    }
    for (std::size_t k = 1; k <= 13; ++k) {
        if (largest_product(DIGITS, k) != largest_product_brute(DIGITS, k)) {
            return 1;
        }
    }
    std::cout << largest_product(DIGITS, 13) << '\n';
    return 0;
}

The 1000-digit number is written as 20 lines of 50 digits. Adjacent string literals are joined into one at compile time. In case a line goes missing or a digit is mistyped, main first checks that the length is 1000 and that every character is between '0' and '9'.

There are three small examples: 3021945 (k = 3 → 180), traced by hand in the derivation; 1020304 (k = 3), where every window contains a zero so the answer must be 0; and the problem’s example (k = 4 → 5832). After that, for k = 1 through 13, the sliding window is compared with largest_product_brute (the brute force). A mistake in the order of updating Z and P, in the division condition, or in the “window is full” condition would be caught by this comparison. The checks use if and return 1 rather than assert, because assert does nothing in a build where NDEBUG is defined.

Python 3

# The 1000-digit number from the problem, 50 digits per line.
DIGITS = (
    "73167176531330624919225119674426574742355349194934"
    "96983520312774506326239578318016984801869478851843"
    "85861560789112949495459501737958331952853208805511"
    "12540698747158523863050715693290963295227443043557"
    "66896648950445244523161731856403098711121722383113"
    "62229893423380308135336276614282806444486645238749"
    "30358907296290491560440772390713810515859307960866"
    "70172427121883998797908792274921901699720888093776"
    "65727333001053367881220235421809751254540594752243"
    "52584907711670556013604839586446706324415722155397"
    "53697817977846174064955149290862569321978468622482"
    "83972241375657056057490261407972968652414535100474"
    "82166370484403199890008895243450658541227588666881"
    "16427171479924442928230863465674813919123162824586"
    "17866458359124566529476545682848912883142607690042"
    "24219022671055626321111109370544217506941658960408"
    "07198403850962455444362981230987879927244284909188"
    "84580156166097919133875499200524063689912560717606"
    "05886116467109405077541002256983155200055935729725"
    "71636269561882670428252483600823257530420752963450"
)


def digit_at(digits: str, i: int) -> int:
    """The value of the digit at position i of a string of '0'..'9'."""
    return ord(digits[i]) - ord("0")


def largest_product(digits: str, k: int) -> int:
    """Largest product of k adjacent digits, for 1 <= k <= len(digits).

    Rolling window: zeros counts the zeros in the window and nonzero_product is the
    product of its other digits, so the window's product is 0 if zeros > 0 and
    nonzero_product otherwise. Only nonzero digits are ever divided out.
    """
    nonzero_product = 1
    zeros = 0
    best = 0
    for i in range(len(digits)):
        if i >= k:
            # Remove the digit leaving the window before adding the new one,
            # so the window never holds more than k digits.
            outgoing = digit_at(digits, i - k)
            if outgoing == 0:
                zeros -= 1
            else:
                nonzero_product //= outgoing
        incoming = digit_at(digits, i)
        if incoming == 0:
            zeros += 1
        else:
            nonzero_product *= incoming
        if i + 1 >= k and zeros == 0 and nonzero_product > best:
            best = nonzero_product
    return best


def largest_product_brute(digits: str, k: int) -> int:
    """Multiplies every window from scratch. Used only to cross-check largest_product."""
    best = 0
    for start in range(len(digits) - k + 1):
        product = 1
        for j in range(start, start + k):
            product *= digit_at(digits, j)
        if product > best:
            best = product
    return best


def main() -> None:
    if len(DIGITS) != 1000:
        raise SystemExit(1)
    for c in DIGITS:
        if c < "0" or c > "9":
            raise SystemExit(1)
    if largest_product("3021945", 3) != 180 or largest_product("1020304", 3) != 0:
        raise SystemExit(1)
    if largest_product(DIGITS, 4) != 5832:
        raise SystemExit(1)
    for k in range(1, 14):
        if largest_product(DIGITS, k) != largest_product_brute(DIGITS, k):
            raise SystemExit(1)
    print(largest_product(DIGITS, 13))


if __name__ == "__main__":
    main()

Same algorithm, same checks as the C++ version. String literals written next to each other inside the parentheses are joined into one, as in C++. A digit’s value is computed with ord(c) - ord("0"), which means the same as the C++ c - '0', and division is used only where it is exact, so the integer division // throws nothing away. If a small example fails, raise SystemExit(1) gives exit status 1. assert is not used because running with python -O removes it.

Answer and checks

The largest product of thirteen adjacent digits is 23514624000.

The parts you can follow by hand:

  • Which window. The window that gives this value is the 198th through 210th digits of the 1000-digit number (counting from 1), 5576689664895: the 557 at the end of the fourth line of the code and the 6689664895 at the start of the fifth. The very next digit, the 211th, is 0.
  • The product. These digits are three 5s, one 7, four 6s, two 8s, two 9s and one 4, so the product is 5³ × 7 × 6⁴ × 8² × 9² × 4 = 125 × 7 × 1296 × 64 × 81 × 4 = 2¹² × 3⁸ × 5³ × 7, which multiplies out to the value above. It is at most 9¹³ and above the 32-bit maximum, so this is a case where the integer bounds under Complexity actually matter.
  • A hand check that no window is larger (for reference). A window containing a zero has product 0, so only the zero-free stretches of length 13 or more need looking at. To reach this value, the geometric mean of the 13 digits must be at least about 6.28. Scoring each digit by how far short of 9 it falls, as a common logarithm (about 0.95 for a 1, 0.65 for a 2, 0.48 for a 3, 0.35 for a 4), the total over a window must be at most about 2.03, so windows with several 1s, 2s or 3s drop out quickly. Going through each stretch this way leaves only the window above. This is a hand calculation, though, and can contain mistakes; the decisive check is the program verification below.

The checks come in three layers.

  1. Small examples and comparison with the brute force. Before printing the answer, both programs check that the copied number is 1000 digits, that 3021945 (k = 3) gives 180, 1020304 (k = 3) gives 0 and the problem’s example (k = 4) gives 5832, and that the sliding window and the brute force agree for every k from 1 to 13. If anything differs, they exit with a nonzero status.
  2. Agreement between the two implementations. In this series’ repository a check script compiles the C++ code with g++ -std=c++17 -O2 -Wall -Wextra -Werror and runs it (warnings count as failures), and runs the Python code with python3 -I -B. Both outputs must match the stored answer.txt byte for byte, and a nonzero exit status or a timeout (1 second for C++, 10 seconds for Python) is a failure. By the series rules only code that passes this check is published.
  3. The proof. That the sliding window sees the exact product of every window, and never divides by zero or performs a division that leaves a remainder, was shown in the derivation and the correctness proof.

Boundary cases

  • k = 1: the window is a single digit and the answer is the largest digit. Removing the leaving digit brings P back to 1 (d / d = 1 if it is nonzero; only Z changes if it is 0). The programs’ comparison includes k = 1.
  • Every window contains a zero: a window with Z > 0 never changes best, so best stays at its starting value 0, which is the right answer (1020304, k = 3).
  • A window a zero has just left: the moment Z returns to 0, P is already the product of the nonzero digits in the window and is therefore the window’s product. Step i = 4 of the trace is this case.
  • k > n: there are no windows and the function returns 0. But it cannot tell “no windows” from “the largest product is 0”, so the function requires k ≤ n.
  • k = 0: outside the precondition. Since i ≥ 0 is always true, it removes a digit that was never added and the invariant breaks (in C++, if that digit is 0, Z goes below 0 and the unsigned value wraps around). Reusing the function would need an input check first.
  • Order of removing and adding: adding before removing gives the same answer, but k + 1 digits are briefly multiplied in and the bound grows to 9¹⁴. The order used here keeps the bound at 9ᵏ.

Going further

  • Longer windows. Since P ≤ 9ᵏ and 9²⁰ (about 1.22 × 10¹⁹) < 2⁶⁴ − 1 (about 1.84 × 10¹⁹) < 9²¹ (about 1.09 × 10²⁰), a 64-bit unsigned long long is safe up to k ≤ 20. For longer windows, C++ would need to handle big integers itself or compare windows some other way than by their products.
  • Comparing sums of logarithms. Comparing products is the same as comparing the sums of their logarithms, which lets you compare windows without overflow. Floating-point error can misorder two nearly equal windows, though, so it is safer to pick candidates that way and then confirm with exact integer products.
  • Without division. A queue built from two stacks, with each stack also storing running products, keeps the window’s product without any division. It has the advantage of working for operations that cannot be undone, such as the maximum in the window. Think about how to make it amortised constant time per digit.
  • Sums instead of products. Ask the same question with sums instead of products and the zero problem disappears: subtraction alone slides the window. With products, zero being a value that “cannot be undone” is what made the Z in this post necessary.

Sources and license

  • Project Euler, Problem 8 — the original problem. The “Problem” section of this post is my own summary of it, and the 1000-digit number copied into the code is taken from the original problem. These parts are shared under the same CC BY-NC-SA 4.0 license as the original. Attribution for the problem goes to Project Euler.
  • Project Euler, Copyright — the license of the problem text and how to link to problems. Because of the non-commercial condition, this post carries no ads (ads: false).
  • The precision of Python’s int follows Numeric Types — int, float, complex, and assert and -O follow The assert statement. The C++ facts (that the values of the digit characters '0' to '9' increase by one at each step, that unsigned long long is at least 64 bits wide, and that assert does nothing when NDEBUG is defined) are requirements of the C++ standard (ISO/IEC 14882).
  • The solution, proofs and code are my own. I did not consult Project Euler’s overviews, forum, member-only material or other solution sites. Motitory is not affiliated with or sponsored by Project Euler, and Project Euler has not reviewed this post.

Back to the blog