# 343. Integer Break
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
Example 1:
Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:
Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Note: You may assume that n is not less than 2 and not larger than 58.
# Solution
Approach 1: DP in O(N^2)
time.
Approach 2: math in O(1)
time: should split whenever there's a number >= 4 -- between 2 and 3, use as many 3s as possible since 3 * 3 > 2 * 2 * 2
for 6.
# Code (Python)
Approach 1:
def integerBreak(self, n: int) -> int:
# DP: table[i] -- integerBreak(i), initialized with table[1] = table[2] = 1
# O(N^2) time
table = [1 for _ in range(n + 1)]
for num in range(3, n + 1):
for component in range(1, num // 2 + 1):
table[num] = max(
table[num],
table[component] * table[num-component],
component * table[num-component],
table[component] * (num - component),
component * (num - component)
)
return table[-1]
Approach 2:
def integerBreak(self, n: int) -> int:
# O(1) math solution: find the critical point where a split is better than a non-split
# x/2 * x/2 >= x => x >= 4 when x is even
# (x-1) / 2 * (x+1) / 2 >= x => x >= 5 when x is odd
# basically it means any number >= 4 should be split into 2 parts with either 2 or 3
# 3 is better than 2 because 3 * 3 > 2 * 2 * 2 (for a sum of 6), so use as many 3s as possible
if n == 2:
return 1
if n == 3:
return 2
num_of_threes = n // 3
remainder = n % 3
if remainder == 0:
return 3 ** num_of_threes
elif remainder == 1:
return 3 ** (num_of_threes - 1) * 2 * 2
else:
return 3 ** num_of_threes * 2
# Code (C++)
Approach 1:
Approach 2: