343. Integer Break - Solution & Explanation

Q: Is Integer Break easy or hard?

Integer Break is generally classified as a Medium difficulty problem. The dynamic programming formulation is straightforward once the recurrence is identified, while the mathematical optimization requires recognizing a pattern about maximizing products using 3s.

Q: Integer Break Python/Java solution

In Python or Java, the dynamic programming solution uses an array of size n+1 and iterates through all split points to compute the maximum product. The mathematical solution calculates the product of powers of 3 with a few conditional checks, resulting in very concise code.

Q: How to solve Integer Break in O(1)?

Use the mathematical observation that the maximum product occurs when the integer is broken into factors of 3. Repeatedly subtract 3 from n and multiply the result until the remaining value is 4 or less. Multiply the remainder with the accumulated product to get the final answer.

Q: What is the best approach for Integer Break?

The mathematical greedy approach is the optimal solution. It relies on the observation that splitting the number into as many 3s as possible maximizes the product. This method runs in O(1) time and O(1) space. In interviews, candidates often start with the dynamic programming solution and then optimize using this mathematical insight.

Q: Is Integer Break asked at Google/Amazon/Meta?

Integer Break appears frequently in coding interview practice sets and has been reported in interviews at companies like Amazon and Google. It tests dynamic programming fundamentals and the ability to derive mathematical optimizations from patterns.

Q: What data structure is used in Integer Break?

The dynamic programming approach uses a simple array dp where dp[i] stores the maximum product obtainable by breaking integer i. The mathematical solution does not require any additional data structure and works with basic arithmetic operations.

The problem

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Example 1:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

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

Constraints:

2 <= n <= 58

Approach overview

Problem Overview: Given an integer n, break it into the sum of at least two positive integers such that the product of those integers is maximized. The task is to return the maximum possible product you can obtain from any valid split.

Approach 1: Dynamic Programming (O(n²) time, O(n) space)

This approach builds the solution bottom-up using dynamic programming. Define dp[i] as the maximum product obtainable by breaking integer i. For every number from 2 to n, iterate through all possible first splits j where 1 ≤ j < i. For each split, compute the best product using either the raw value (i - j) or the previously computed value dp[i - j]. The recurrence becomes dp[i] = max(dp[i], j * (i - j), j * dp[i - j]). This ensures every partition combination is considered while reusing previously computed results. The nested iteration leads to O(n²) time complexity and O(n) space.

Approach 2: Mathematical Greedy Insight (O(1) time, O(1) space)

The optimal solution comes from a key observation in math: splitting numbers into as many 3s as possible produces the maximum product. For example, 10 = 3 + 3 + 4 gives product 36, which is larger than other splits like 5 + 5. The reason is that 3 provides the best multiplicative growth compared to larger segments. Special cases occur when the remainder becomes 1; instead of 3 + 1, convert it into 2 + 2 because 2 × 2 is larger than 3 × 1. The algorithm repeatedly subtracts 3 from n and multiplies the result until the remaining value is ≤ 4, then multiplies the remainder. This produces the optimal product in constant time and space.

Recommended for interviews: The dynamic programming solution demonstrates strong problem-solving fundamentals and is the approach most candidates derive during interviews. It clearly shows how subproblems combine to form the optimal answer. The mathematical approach is the true optimal solution and often appears as a follow-up optimization once you recognize the pattern that breaking numbers into 3s maximizes the product.

Approach 1: Dynamic Programming Approach

The dynamic programming approach involves creating an array dp where dp[i] represents the maximum product obtainable for the integer i. The idea is to iterate through numbers from 2 to n and for each number, explore all possible ways to split it into two positive integers j and i-j. The solution for each i is derived by taking the maximum of j * (i-j) or j * dp[i-j] for all j from 1 to i-1.

Python

def integerBreak(n):
    if n <= 3:
        return n - 1
    dp = [0] * (n + 1)
    dp[2], dp[3] = 1, 2
    for i in range(4, n + 1):
        for j in range(1, i):
            dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
    return dp[n]

n = 10
print(f"Maximum product for {n} is {integerBreak(n)}")

Java

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

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Maximum product for " + n + " is " + integerBreak(n));
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

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

int main() {
    int n = 10;
    cout << "Maximum product for " << n << " is " << integerBreak(n) << endl;
    return 0;
}

JavaScript

function integerBreak(n) {
    if (n <= 3) return n - 1;
    let dp = Array(n + 1).fill(0);
    dp[2] = 1;
    dp[3] = 2;
    for (let i = 4; i <= n; ++i) {
        for (let j = 1; j < i; ++j) {
            dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
        }
    }
    return dp[n];
}

let n = 10;
console.log(`Maximum product for ${n} is ${integerBreak(n)}`);

#include <stdio.h>

int integerBreak(int n) {
    if (n <= 3) return n - 1;
    int dp[n + 1];
    dp[0] = dp[1] = 0;
    dp[2] = 1;
    dp[3] = 2;
    for (int i = 4; i <= n; ++i) {
        dp[i] = 0;
        for (int j = 1; j < i; ++j) {
            dp[i] = dp[i] > j * (i - j) ? dp[i] : j * (i - j);
            dp[i] = dp[i] > j * dp[i - j] ? dp[i] : j * dp[i - j];
        }
    }
    return dp[n];
}

int main() {
    int n = 10;
    printf("Maximum product for %d is %d\n", n, integerBreak(n));
    return 0;
}

using System;

public class Solution {
    public int IntegerBreak(int n) {
        if (n <= 3) return n - 1;
        int[] dp = new int[n + 1];
        dp[2] = 1;
        dp[3] = 2;
        for (int i = 4; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                dp[i] = Math.Max(dp[i], Math.Max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }

    public static void Main(string[] args) {
        int n = 10;
        Console.WriteLine("Maximum product for " + n + " is " + new Solution().IntegerBreak(n));
    }
}

This Python solution applies a bottom-up DP approach where dp[i] stores the maximum product obtainable for integer i. The outer loop iterates through numbers from 4 to n, while an inner loop splits i into two parts to find the optimal product.

Complexity

Time Complexity: O(n^2) because we process two nested loops.
Space Complexity: O(n) for the dp list.

Try this approach in the editor

Approach 2: Mathematical Approach

The mathematical approach relies on the observation that numbers are best broken down into 2s and 3s to maximize their product. In particular, the number 3 plays a critical role. For any number greater than 4, it is beneficial to use as many 3s as possible, because any larger piece can be expressed as 3k + r, where adding more 3s generally yields a larger product (e.g., breaking 4 into 2 + 2 is optimal, compared to using one 3 and a 1). The approach is to keep factoring out 3 from n as long as the remaining part is not less than 4, then multiply the results together to get the maximum product.

Python

def integerBreak(n):
    if n <= 3:
        return n - 1
    product = 1
    while n > 4:
        product *= 3
        n -= 3
    return product * n

n = 10
print(f"Maximum product for {n} is {integerBreak(n)}")

Java

class Main {
    public static int integerBreak(int n) {
        if (n <= 3) return n - 1;
        int product = 1;
        while (n > 4) {
            product *= 3;
            n -= 3;
        }
        return product * n;
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Maximum product for " + n + " is " + integerBreak(n));
    }
}

C++

#include <iostream>
using namespace std;

int integerBreak(int n) {
    if (n <= 3) return n - 1;
    int product = 1;
    while (n > 4) {
        product *= 3;
        n -= 3;
    }
    return product * n;
}

int main() {
    int n = 10;
    cout << "Maximum product for " << n << " is " << integerBreak(n) << endl;
    return 0;
}

JavaScript

function integerBreak(n) {
    if (n <= 3) return n - 1;
    let product = 1;
    while (n > 4) {
        product *= 3;
        n -= 3;
    }
    return product * n;
}

let n = 10;
console.log(`Maximum product for ${n} is ${integerBreak(n)}`);

#include <stdio.h>

int integerBreak(int n) {
    if (n <= 3) return n - 1;
    int product = 1;
    while (n > 4) {
        product *= 3;
        n -= 3;
    }
    return product * n;
}

int main() {
    int n = 10;
    printf("Maximum product for %d is %d\n", n, integerBreak(n));
    return 0;
}

using System;

public class Solution {
    public int IntegerBreak(int n) {
        if (n <= 3) return n - 1;
        int product = 1;
        while (n > 4) {
            product *= 3;
            n -= 3;
        }
        return product * n;
    }

    public static void Main(string[] args) {
        int n = 10;
        Console.WriteLine("Maximum product for " + n + " is " + new Solution().IntegerBreak(n));
    }
}

This Python solution utilizes a mathematical method to achieve an efficient result. The integer is repeatedly reduced by factors of 3, ensuring optimal chunks for maximizing the final product.

Complexity

Time Complexity: O(log n) due to decrementing in steps of 3.
Space Complexity: O(1) because no additional space is used for storage.

Try this approach in the editor

Approach 3: Dynamic Programming

We define f[i] as the maximum product that can be obtained by splitting the positive integer i, with an initial condition of f[1] = 1. The answer is f[n].

Consider the last number j split from i, where j \in [1, i). For the number j split from i, there are two cases:

Split i into the sum of i - j and j, without further splitting, where the product is (i - j) times j;
Split i into the sum of i - j and j, and continue splitting, where the product is f[i - j] times j.

Therefore, we can derive the state transition equation:

$f[i] = max(f[i], f[i - j] times j, (i - j) times j) \quad (j \in [0, i))

Finally, returning f[n] will suffice.

The time complexity is O(n^2), and the space complexity is O(n). Here, n$ is the given positive integer.

TypeScript

function integerBreak(n: number): number {
    const f = Array(n + 1).fill(1);
    for (let i = 3; i <= n; i++) {
        for (let j = 1; j < i; j++) {
            f[i] = Math.max(f[i], j * (i - j), j * f[i - j]);
        }
    }
    return f[n];
}

func integerBreak(n int) int {
	f := make([]int, n+1)
	f[1] = 1
	for i := 2; i <= n; i++ {
		for j := 1; j < i; j++ {
			f[i] = max(max(f[i], f[i-j]*j), (i-j)*j)
		}
	}
	return f[n]
}

Rust

impl Solution {
    pub fn integer_break(n: i32) -> i32 {
        let n = n as usize;
        let mut f = vec![0; n + 1];
        f[1] = 1;
        for i in 2..=n {
            for j in 1..i {
                f[i] = f[i].max(f[i - j] * j).max((i - j) * j);
            }
        }
        f[n] as i32
    }
}

Try this approach in the editor

Approach 4: Mathematics

When n < 4, since the problem requires splitting into at least two integers, n - 1 yields the maximum product. When n geq 4, we split into as many 3s as possible. If the last segment remaining is 4, we split it into 2 + 2 for the maximum product.

The time complexity is O(1), and the space complexity is O(1).

TypeScript

function integerBreak(n: number): number {
    if (n < 4) {
        return n - 1;
    }
    const m = Math.floor(n / 3);
    if (n % 3 == 0) {
        return 3 ** m;
    }
    if (n % 3 == 1) {
        return 3 ** (m - 1) * 4;
    }
    return 3 ** m * 2;
}

func integerBreak(n int) int {
	if n < 4 {
		return n - 1
	}
	if n%3 == 0 {
		return int(math.Pow(3, float64(n/3)))
	}
	if n%3 == 1 {
		return int(math.Pow(3, float64(n/3-1))) * 4
	}
	return int(math.Pow(3, float64(n/3))) * 2
}

Rust

impl Solution {
    pub fn integer_break(n: i32) -> i32 {
        if n < 4 {
            return n - 1;
        }
        match n % 3 {
            0 => return (3 as i32).pow((n / 3) as u32),
            1 => return (3 as i32).pow((n / 3 - 1) as u32) * 4,
            _ => return (3 as i32).pow((n / 3) as u32) * 2,
        }
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming Approach	Time Complexity: O(n^2) because we process two nested loops. Space Complexity: O(n) for the dp list.
Mathematical Approach	Time Complexity: O(log n) due to decrementing in steps of 3. Space Complexity: O(1) because no additional space is used for storage.
Dynamic Programming	–
Mathematics	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming	O(n^2)	O(n)	Best for interviews when deriving the solution from first principles and demonstrating DP reasoning.
Mathematical Greedy	O(1)	O(1)	Use when you recognize the mathematical pattern that splitting into 3s maximizes product.

Frequently asked questions

Is Integer Break easy or hard?

Integer Break is generally classified as a Medium difficulty problem. The dynamic programming formulation is straightforward once the recurrence is identified, while the mathematical optimization requires recognizing a pattern about maximizing products using 3s.

Integer Break Python/Java solution

In Python or Java, the dynamic programming solution uses an array of size n+1 and iterates through all split points to compute the maximum product. The mathematical solution calculates the product of powers of 3 with a few conditional checks, resulting in very concise code.

How to solve Integer Break in O(1)?

Use the mathematical observation that the maximum product occurs when the integer is broken into factors of 3. Repeatedly subtract 3 from n and multiply the result until the remaining value is 4 or less. Multiply the remainder with the accumulated product to get the final answer.

What is the best approach for Integer Break?

The mathematical greedy approach is the optimal solution. It relies on the observation that splitting the number into as many 3s as possible maximizes the product. This method runs in O(1) time and O(1) space. In interviews, candidates often start with the dynamic programming solution and then optimize using this mathematical insight.

Is Integer Break asked at Google/Amazon/Meta?

Integer Break appears frequently in coding interview practice sets and has been reported in interviews at companies like Amazon and Google. It tests dynamic programming fundamentals and the ability to derive mathematical optimizations from patterns.

What data structure is used in Integer Break?

The dynamic programming approach uses a simple array <code>dp</code> where dp[i] stores the maximum product obtainable by breaking integer i. The mathematical solution does not require any additional data structure and works with basic arithmetic operations.

What is the time complexity of Integer Break?

The dynamic programming solution runs in O(n^2) time because for every integer i you iterate through all possible splits j from 1 to i-1. The optimized mathematical approach reduces this to O(1) time by directly computing the product using powers of 3.

Integer Break solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Mathematical Approach

Approach 3: Dynamic Programming

Approach 4: Mathematics

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Integer Break solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Mathematical Approach

Approach 3: Dynamic Programming

Approach 4: Mathematics

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems