AlgoMaster Logo

Integer Break

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

The question asks us to split a number into at least two positive parts and make the product of those parts as large as possible. For small numbers this is easy to verify by hand, but the real challenge is figuring out a general strategy for any n up to 58.

Consider n = 6. We could split it as 3 + 3 (product 9), 2 + 4 (product 8), 2 + 2 + 2 (product 8), or 1 + 5 (product 5). The best split is 3 + 3. The factor 3 recurs across the best splits because among all positive integers, 3 gives the best product per unit when used as a factor. The reason for that leads directly to the optimal solution.

Key Constraints:

  • 2 <= n <= 58 -> With n at most 58, even an O(n^2) solution runs fast. The answer also stays within a 32-bit signed integer (the largest result is 3^19 = 1,162,261,467 for n = 57), so a plain int does not overflow.
  • k >= 2 -> We must split n into at least two parts. This matters for the small cases n = 2 and n = 3, where any split lowers the value below n itself.

Approach 1: Brute Force (Recursion)

Intuition

Try every way to split off a first part i, leaving n - i. The left part i stays whole. The right part n - i is either kept whole or broken down further by solving the same problem on it. Taking the maximum over all split points i gives the answer for n.

Algorithm

  1. For each split point i from 1 to n - 1, consider breaking n into i and n - i.
  2. For the second part n - i, we have two choices: keep it as n - i or recursively break it to get integerBreak(n - i).
  3. The product for this split is i * max(n - i, integerBreak(n - i)).
  4. Return the maximum product across all split points.

Example Walkthrough

Input:

6
n

For n = 6, the recursion first needs the answers for the smaller values it depends on. The base cases give integerBreak(2) = 1 and integerBreak(3) = 2. From those:

  • integerBreak(4): best split is i = 2, giving 2 * max(2, integerBreak(2)=1) = 2 * 2 = 4.
  • integerBreak(5): best split is i = 2, giving 2 * max(3, integerBreak(3)=2) = 2 * 3 = 6.

Now the top-level call for n = 6 tries each split point:

Scroll

i

n - i

break(n - i)

i * max(n - i, break(n - i))

1

5

6

1 * max(5, 6) = 6

2

4

4

2 * max(4, 4) = 8

3

3

2

3 * max(3, 2) = 9

4

2

1

4 * max(2, 1) = 8

5

1

1

5 * max(1, 1) = 5

The maximum across all rows is 9, from the split 3 + 3.

9
result

Code

Computing integerBreak(6) recomputed integerBreak(4), integerBreak(3), and integerBreak(2) many times across different branches. Storing each result the first time it is computed removes the repeated work.

Approach 2: Dynamic Programming (Bottom-Up)

Intuition

The recursive solution recomputes overlapping subproblems, so dynamic programming applies. Instead of recomputing integerBreak(k) every time it is needed, build the answers bottom-up from 2 to n and store each result in an array, so every later value reads its dependencies directly.

Algorithm

  1. Create an array dp of size n + 1, where dp[j] represents the maximum product for integer j.
  2. Base case: dp[2] = 1 (only split is 1 + 1).
  3. For each j from 3 to n:
    • For each i from 1 to j - 1:
      • dp[j] = max(dp[j], i * max(j - i, dp[j - i])).
  4. Return dp[n].

Example Walkthrough

1Initialize dp array, dp[2] = 1 (base case: 1+1 = 1)
0
0
1
0
2
1
3
0
4
0
5
0
6
0
7
0
8
0
9
0
10
0
1/9

Code

Approach 3: Greedy (Math)

Intuition

The optimal split uses as many 3s as possible. Three rules justify this:

  • A factor of 1 never helps: removing a 1 and adding it to any other factor increases the product (k > k * 1), so the optimal split contains no 1s.
  • No factor should be 5 or more: any f >= 5 can be replaced by 3 + (f - 3), and 3 * (f - 3) > f once f >= 5 (for example 5 -> 3 2 = 6, 6 -> 3 3 = 9). So every factor in the optimal split is 2, 3, or 4. A 4 is left as-is because 2 * 2 = 4, the same as keeping it whole.
  • Prefer 3 over 2: three 2s sum to 6 and multiply to 8, while two 3s sum to 6 and multiply to 9. So whenever the remaining amount is 6 or more, splitting off a 3 beats splitting off a 2.

That leaves the leftover after taking out 3s, which is n % 3. If the remainder is 0, all 3s are used. If it is 2, that 2 is kept as its own factor. If it is 1, one 3 is combined with the leftover 1 into a 4 (used as 2 2 = 4), because `2 2 = 4 beats 3 * 1 = 3`.

Algorithm

  1. If n == 2, return 1. If n == 3, return 2. (Must split, so 1 1 and 1 2.)
  2. If n % 3 == 0, the answer is 3^(n/3).
  3. If n % 3 == 1, give back one 3, use two 2s: answer is 3^(n/3 - 1) * 4.
  4. If n % 3 == 2, use one extra 2: answer is 3^(n/3) * 2.

Example Walkthrough:

1Start: n=10, check n%3 = 10%3 = 1
10
1/5

Code