Integer Break - Video Solutions

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.