Integer Break

Medium
323.

Integer Break

Integer Break is a medium coding problem on dynamic programming and math, asked in Amazon and Google interviews.

Given an integer n, break it into the sum of at least two positive integers and maximise the product of those integers.

Return the maximum product you can obtain.

Example 1

Input
n = 2
Output
1
Explanation
2 = 1 + 1, so the product is 1.

Example 2

Input
n = 10
Output
36
Explanation
10 = 3 + 3 + 4.

Example 3

Input
n = 4
Output
4
Explanation
4 = 2 + 2.

Constraints

  • 2 <= n <= 40
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Integer Break — Solution in Python, Java & C++

Integer Break solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Integer Break is a medium coding problem on dynamic programming and math, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Dynamic Programming, Math
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an integer n, break it into the sum of at least two positive integers and maximise the product of those integers.

Return the maximum product you can obtain.

Example 1

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, so the product is 1.

Example 2

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4.

Example 3

Input: n = 4
Output: 4
Explanation: 4 = 2 + 2.

Constraints

  • 2 <= n <= 40

Hints for Integer Break

  1. Hint 1

    For each first piece k, you may either stop there — product k × (n - k) — or break the remainder further, giving k × dp[n - k].

  2. Hint 2

    Take the larger of those two for every k, and the maximum over all k.

  3. Hint 3

    The greedy answer uses as many 3s as possible, which the DP will reproduce.

How to solve Integer Break

For each first piece k, either stop (k · (n-k)) or keep breaking the remainder (k · dp[n-k]); take the best over all k.

Approach

  1. Set dp[1] = 1.
  2. For i from 2 to n and k from 1 to i-1, dp[i] = max(dp[i], k·(i-k), k·dp[i-k]).
  3. Return dp[n].

Why it works

dp[i] is the best product of a break into at least two parts; allowing "stop after one split" separately is what handles the at-least-two rule at the top level while still letting sub-breaks use a single piece.

Complexity

  • Time — O(n²)
  • Space — O(n)

Pitfalls

  • The greedy answer uses as many 3s as possible (with a 4 or 2 at the end) — the DP reproduces it and is easier to justify.

Reference solution

Python

def integerBreak(n: int) -> int:
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        for k in range(1, i):
            dp[i] = max(dp[i], k * (i - k), k * dp[i - k])
    return dp[n]

Java

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

C++

int integerBreak(int n) {
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int k = 1; k < i; k++) {
            dp[i] = max(dp[i], max(k * (i - k), k * dp[i - k]));
        }
    }
    return dp[n];
}

JavaScript

var integerBreak = function(n) {
    const dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        for (let k = 1; k < i; k++) {
            const candidate = Math.max(k * (i - k), k * dp[i - k]);
            if (candidate > dp[i]) dp[i] = candidate;
        }
    }
    return dp[n];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming