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.

Examples

Example 1:

1
2
3

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

Example 2:

1
2
3

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

Solution

Method 1 – Dynamic Programming

Intuition

We want to break the integer n into at least two positive integers such that their product is maximized. For each number i, let dp[i] to be the max production value for breaking the number i. Since dp[i+j] can be i*j,

1

dp[i+j] = max(max(dp[i], i) * max(dp[j], j)), dp[i+j])

So, we can try every possible first split j (where 1 ≤ j < i) and take the maximum between splitting further (dp[i-j]) or not splitting (i-j). This way, we build up the solution from smaller numbers.

Approach

  1. Initialize a DP array dp of size n+1 with all zeros.
  2. Set dp[1] = 1 (base case).
  3. For each i from 2 to n, do:
  • For each j from 1 to i-1:
    • Compute the product of j and the maximum of dp[i-j] and i-j.
    • Update dp[i] with the maximum value found.
  1. Return dp[n] as the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
   int integerBreak(int n) {
      std::vector<int> dp(n + 1, 0);
      dp[1] = 1;
      for (int i = 2; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
           dp[i] = std::max(dp[i], j * std::max(dp[i - j], i - j));
        }
      }
      return dp[n];
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

type Solution struct{}

func (Solution) IntegerBreak(n int) int {
   dp := make([]int, n+1)
   dp[1] = 1
   for i := 2; i <= n; i++ {
      for j := 1; j < i; j++ {
        prod := j
        if dp[i-j] > i-j {
           prod *= dp[i-j]
        } else {
           prod *= i - j
        }
        if prod > dp[i] {
           dp[i] = prod
        }
      }
   }
   return dp[n]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
   public int integerBreak(int n) {
      int[] dp = new int[n + 1];
      dp[1] = 1;
      for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
           dp[i] = Math.max(dp[i], j * Math.max(dp[i - j], i - j));
        }
      }
      return dp[n];
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
   fun integerBreak(n: Int): Int {
      val dp = IntArray(n + 1)
      dp[1] = 1
      for (i in 2..n) {
        for (j in 1 until i) {
           dp[i] = maxOf(dp[i], j * maxOf(dp[i - j], i - j))
        }
      }
      return dp[n]
   }
}
1
2
3
4
5
6
7
8

class Solution:
   def integerBreak(self, n: int) -> int:
      dp: list[int] = [0] * (n + 1)
      dp[1] = 1
      for i in range(2, n + 1):
        for j in range(1, i):
           dp[i] = max(dp[i], j * max(dp[i - j], i - j))
      return dp[n]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(n)

Method 2 - Using Regularities

If we see the breaking result for some numbers, we can see repeated pattern like the following:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

2 -> 1*1
3 -> 1*2
4 -> 2*2
5 -> 3*2
6 -> 3*3
7 -> 3*4
8 -> 3*3*2
9 -> 3*3*3
10 -> 3*3*4
11 -> 3*3*3*2

We only need to find how many 3’s we can get when n> 4. If n%3==1, we do not want 1 to be one of the broken numbers, we want 4.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        if (n == 4) return 4;
        int result = 1;
        if (n % 3 == 0) {
            int m = n / 3;
            for (int i = 0; i < m; ++i) result *= 3;
        } else if (n % 3 == 2) {
            int m = n / 3;
            for (int i = 0; i < m; ++i) result *= 3;
            result *= 2;
        } else if (n % 3 == 1) {
            int m = (n - 4) / 3;
            for (int i = 0; i < m; ++i) result *= 3;
            result *= 4;
        }
        return result;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func integerBreak(n int) int {
    if n == 2 {
        return 1
    }
    if n == 3 {
        return 2
    }
    if n == 4 {
        return 4
    }
    result := 1
    if n%3 == 0 {
        m := n / 3
        for i := 0; i < m; i++ {
            result *= 3
        }
    } else if n%3 == 2 {
        m := n / 3
        for i := 0; i < m; i++ {
            result *= 3
        }
        result *= 2
    } else if n%3 == 1 {
        m := (n - 4) / 3
        for i := 0; i < m; i++ {
            result *= 3
        }
        result *= 4
    }
    return result
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
	public int integerBreak(int n) {
	
		if (n == 2) return 1;
		if (n == 3) return 2;
		if (n == 4) return 4;
	
		int result = 1;
		if (n % 3 == 0) {
			int m = n / 3;
			result = (int) Math.pow(3, m);
		} else if (n % 3 == 2) {
			int m = n / 3;
			result = (int) Math.pow(3, m) * 2;
		} else if (n % 3 == 1) {
			int m = (n - 4) / 3;
			result = (int) Math.pow(3, m) * 4;
		}
	
		return result;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun integerBreak(n: Int): Int {
        if (n == 2) return 1
        if (n == 3) return 2
        if (n == 4) return 4
        var result = 1
        if (n % 3 == 0) {
            val m = n / 3
            repeat(m) { result *= 3 }
        } else if (n % 3 == 2) {
            val m = n / 3
            repeat(m) { result *= 3 }
            result *= 2
        } else if (n % 3 == 1) {
            val m = (n - 4) / 3
            repeat(m) { result *= 3 }
            result *= 4
        }
        return result
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def integerBreak(self, n: int) -> int:
        if n == 2:
            return 1
        if n == 3:
            return 2
        if n == 4:
            return 4
        result = 1
        if n % 3 == 0:
            m = n // 3
            result = 3 ** m
        elif n % 3 == 2:
            m = n // 3
            result = (3 ** m) * 2
        elif n % 3 == 1:
            m = (n - 4) // 3
            result = (3 ** m) * 4
        return result
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

impl Solution {
    pub fn integer_break(n: i32) -> i32 {
        if n == 2 { return 1; }
        if n == 3 { return 2; }
        if n == 4 { return 4; }
        let mut result = 1;
        if n % 3 == 0 {
            let m = n / 3;
            for _ in 0..m {
                result *= 3;
            }
        } else if n % 3 == 2 {
            let m = n / 3;
            for _ in 0..m {
                result *= 3;
            }
            result *= 2;
        } else if n % 3 == 1 {
            let m = (n - 4) / 3;
            for _ in 0..m {
                result *= 3;
            }
            result *= 4;
        }
        result
    }
}

Complexity

  • ⏰ Time complexity: O(1). All operations are constant time for reasonable n, as n ≤ 58 for Leetcode
  • 🧺 Space complexity: O(1). no extra space used except a few variables