Interview Question Series | Season 3

Problem Overview

You are given:

An integer n

Your task is to:

Break n into the sum of k positive integers where:

k >= 2

And maximize the product of those integers.

Return:

The maximum possible product.

This problem is popular in interviews because it tests:

Mathematical optimization
Greedy thinking
Pattern recognition
Number theory intuition
Converting DP problems into mathematical solutions

Example

Example 1

Input:

n = 2

Output:

Explanation:

2 = 1 + 1
1 × 1 = 1

Example 2

Input:

n = 10

Output:

Explanation:

10 = 3 + 3 + 4
3 × 3 × 4 = 36

Approach 1: Brute Force Idea

Idea:

Try every possible way to split n into positive integers.

For each split:

Calculate the product
Keep the maximum answer

Disadvantages:

Huge number of combinations
Exponential complexity
Too slow for larger values

We need a mathematical observation.

Best Approach: Greedy + Math

Core Observation

Suppose we want to maximize a product.

Let’s see what happens when we split numbers:

Split 5

Product:

Split into:

2 + 3

Product:

2 × 3 = 6

Better ✅

Split 6

3 + 3

Product:

Better than:

2 + 2 + 2 = 8

Split 8

3 + 3 + 2

Product:

Better than:

4 + 4 = 16

Key Mathematical Insight

To maximize the product:

👉 Break the number into as many 3s as possible.

Because:

3 × (x - 3)

produces a larger product than keeping larger numbers together.

So our strategy becomes:

Use as many 3s as possible.
Handle the remainder carefully.

Three Possible Cases

After dividing by 3:

n % 3

can only be:

0, 1, or 2

Case 1: Remainder = 0

Example:

n = 12

Split:

3 + 3 + 3 + 3

Product:

3^4 = 81

Formula:

3^(n/3)

Case 2: Remainder = 1

Example:

n = 10

Naively:

3 + 3 + 3 + 1

Product:

Bad ❌

Instead:

Take one 3 and combine it with 1:

3 + 1 = 4

Now:

3 + 3 + 4

Product:

Much better ✅

Formula:

3^(n/3 - 1) × 4

Case 3: Remainder = 2

Example:

n = 11

Split:

3 + 3 + 3 + 2

Product:

Formula:

3^(n/3) × 2

Step-by-Step Example

Input

n = 10

Step 1

10 % 3 = 1

Remainder is 1.

Step 2

Use Case 2:

3^(10/3 - 1) × 4

3^2 × 4

9 × 4

Output

Why This Works

The key insight is:

Splitting into 3s gives the maximum growth in product.
A remainder of 1 should never be left alone.
Convert:

3 + 1

into:

2 + 2

because:

2 × 2 = 4

is greater than:

3 × 1 = 3

This leads to the optimal greedy solution.

Time and Space Complexity

Time Complexity

O(1)

Only a few mathematical operations are performed.

Space Complexity

O(1)

No extra data structures are used.

Final Code (Optimized)

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;

        if (n % 3 == 0)
            return pow(3, n / 3);

        if (n % 3 == 1)
            return pow(3, n / 3 - 1) * 4;

        return pow(3, n / 3) * 2;
    }
};