Room 04 · The Grind — 1-D Dynamic Programming

Integer Break

MEDIUM✓ CHIP-TIMEDLC #343 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: Split a whole number n into two or more positive integers that add back up to n, and maximize the product of those parts — pick the split that multiplies out the biggest.

A whole number n arrives, and the task is to break it into two or more positive integer pieces that add back up to n, choosing the split that makes the pieces' product as large as possible.

At least two pieces are required — leaving n unbroken is not a valid answer, even if breaking it would lower the product. Any number of pieces beyond two is allowed, and pieces can repeat in value.

The output is the single largest product achievable across every possible way of splitting n this way.

n is at least 2, so a split into two positive pieces is always possible
the number must be broken into two or more parts, never left whole
parts are positive integers and can repeat in value
only the maximum product is required, not the split itself

EX 01

n = 2

→ 1

minimum size, forced 1 + 1

EX 02

n = 4

→ 4

2 + 2 beats 3 + 1

EX 03

n = 5

→ 6

2 + 3

The hintstake only what you need

HINT 1 THE NUDGE

The last cut you make turns a size-i problem into: some piece k, times whatever is best for the rest — either left whole or broken again. What recurrence captures 'broken again, or not'?

HINT 2 THE STRUCTURE

best(i) = the max over every first piece k < i of max(k · (i − k), k · best(i − k)) — the (i − k) itself is a candidate too, since it might be better left unbroken.

HINT 3 ONE STEP FROM THE ANSWER

That table is correct but there's a closed form hiding in it: the product is maximized by cutting into as many 3s as possible, trading a lone leftover 1 for a 4, or keeping a leftover 2 as-is.

Coach's boardthe pattern, step by step

GREEDY THREESPATTERN · GREEDY THREESn = 11

RUNNING PRODUCT

— empty —

STEP 1

11 breaks into as many 3s as possible: 11 = 3 + 3 + 3 + 2 — the leftover 2 stays whole since splitting it further only shrinks the product.

STEP 1 / 6 · ← → WORK TOO

The splitstwo paces, two languages

grind/integer-break.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def integerBreak(self, n: int) -> int:
        if n == 2:
            return 1
        if n == 3:
            return 2
        quotient, remainder = divmod(n, 3)
        if remainder == 0:
            return 3 ** quotient
        if remainder == 1:
            # a lone leftover 1 is wasted — trade a 3 for a 4 instead (3*1 < 4)
            return 3 ** (quotient - 1) * 4
        return 3 ** quotient * 2

TIME O(LOG N)SPACE O(1)PYTHON · RACE PACE · 13 LN

class Solution:
    def integerBreak(self, n: int) -> int:
        best = [0] * (n + 1)
        best[1] = 1
        for i in range(2, n + 1):
            for k in range(1, i):
                # k paired with the rest left whole, or the rest broken again
                best[i] = max(best[i], k * (i - k), k * best[i - k])
        return best[n]

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 9 LN

class Solution {
    public int integerBreak(int n) {
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        int quotient = n / 3;
        int remainder = n % 3;
        if (remainder == 0) {
            return (int) Math.pow(3, quotient);
        }
        if (remainder == 1) {
            return (int) (Math.pow(3, quotient - 1) * 4);
        }
        return (int) (Math.pow(3, quotient) * 2);
    }
}

TIME O(LOG N)SPACE O(1)JAVA · RACE PACE · 19 LN

class Solution {
    public int integerBreak(int n) {
        int[] best = new int[n + 1];
        best[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int k = 1; k < i; k++) {
                best[i] = Math.max(best[i], Math.max(k * (i - k), k * best[i - k]));
            }
        }
        return best[n];
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 12 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED