Scale Engineer

Integer Break

Med
#0330Time: O(2^n) - The time complexity is exponential because each call can result in multiple recursive calls, leading to a tree of computations where subproblems are repeatedly solved.Space: O(n) - The space complexity is determined by the maximum depth of the recursion stack, which can go up to `n`.1 company
Patterns
MathDynamic Programming
Companies
Accenture

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This is a direct recursive solution that explores all possible ways to partition the integer n. For any number k, it tries every possible first part j and recursively solves for the remaining part k-j. This leads to an exponential number of computations as subproblems are solved repeatedly without any caching.

Algorithm

  • Create a recursive function solve(k) that computes the maximum product for integer k.
  • The base case for the recursion is that for any subproblem num <= 3, it's optimal to not break it further, so we return num itself.
  • For a given num, iterate through all possible first parts i from 1 to num-1.
  • For each i, the remaining part is num-i. The product can be either i * (num-i) or i * solve(num-i) if we break num-i further. We take the maximum of these two possibilities.
  • The function returns the maximum product found across all choices of i.
  • The main function handles the edge cases n=2 and n=3 separately, as n must be broken into at least two parts, and then calls the recursive function for n.

Walkthrough

The core idea is to define a function solve(k) that returns the maximum product for breaking integer k. To compute solve(k), we iterate through all possible first numbers j from 1 to k-1. For each j, the remaining part is k-j. We have two choices for this remaining part:

  1. Use k-j as a factor directly. The product is j * (k-j).
  2. Break k-j further by calling solve(k-j). The product is j * solve(k-j). We take the maximum of these two choices for each j and then the maximum over all possible j. The recurrence relation is solve(k) = max_{1 <= j < k} (j * max(k-j, solve(k-j))). This approach is very slow because it re-calculates the solution for the same subproblems multiple times, leading to an exponential time complexity.
class Solution {    public int integerBreak(int n) {        if (n <= 3) {            return n - 1;        }        return solve(n);    }        private int solve(int num) {        if (num <= 3) {            return num;        }        int maxProd = 0;        for (int i = 1; i < num; i++) {            // For the number `num`, we can break it into `i` and `num-i`.            // We can either use `num-i` as is, or break it further.            // The max product for breaking `num-i` is `solve(num-i)`.            // So we take the max of `num-i` and `solve(num-i)`.            int currentProd = i * Math.max(num - i, solve(num - i));            if (currentProd > maxProd) {                maxProd = currentProd;            }        }        return maxProd;    }}

Complexity

Time

O(2^n) - The time complexity is exponential because each call can result in multiple recursive calls, leading to a tree of computations where subproblems are repeatedly solved.

Space

O(n) - The space complexity is determined by the maximum depth of the recursion stack, which can go up to `n`.

Trade-offs

Pros

  • Simple to understand as it directly translates the problem's recursive structure.

Cons

  • Extremely inefficient due to a large number of redundant computations.

  • Will result in a 'Time Limit Exceeded' error on most platforms for moderately large n (e.g., n > 20).

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem