# LeetCode 343: Integer Break ## Problem Restatement We are given an integer `n`. We must break `n` into the sum of at least two positive integers. Among all possible breaks, return the maximum product of those integers. For example: ```text 10 = 3 + 3 + 4 ``` The product is: ```text 3 * 3 * 4 = 36 ``` So for `n = 10`, the answer is `36`. The constraints are: ```text 2 <= n <= 58 ``` The problem statement asks to break `n` into `k` positive integers where `k >= 2`, then maximize the product. ## Input and Output | Item | Meaning | |---|---| | Input | Integer `n` | | Output | Maximum product after breaking `n` | | Break rule | Must use at least two positive integers | | Constraint | `2 <= n <= 58` | Function shape: ```python def integerBreak(n: int) -> int: ... ``` ## Examples Example 1: ```text Input: n = 2 Output: 1 ``` Explanation: ```text 2 = 1 + 1 1 * 1 = 1 ``` Example 2: ```text Input: n = 10 Output: 36 ``` Explanation: ```text 10 = 3 + 3 + 4 3 * 3 * 4 = 36 ``` ## First Thought: Try Every Break A direct recursive idea is: For every possible first part `x`, recursively solve the remaining value `n - x`. But there is a detail. After we split `n` into: ```text x + (n - x) ``` we have two choices for the second part: 1. Keep `n - x` as one number. 2. Break `n - x` further. So the best product for this split is: ```text x * max(n - x, best product after breaking n - x) ``` This naturally leads to dynamic programming. ## Key Insight Let: ```text dp[i] = maximum product obtainable by breaking integer i ``` For each `i`, try every first part `x` from `1` to `i - 1`. The remaining part is: ```text i - x ``` For that remaining part, we choose the better of: | Choice | Product | |---|---:| | Do not break it further | `x * (i - x)` | | Break it further | `x * dp[i - x]` | So the transition is: ```text dp[i] = max(dp[i], x * (i - x), x * dp[i - x]) ``` This works because the original number must be broken at least once, but after that, each remaining part may or may not be broken further. ## Algorithm Create an array `dp` of length `n + 1`. Set: ```python dp[1] = 1 ``` Then for every `i` from `2` to `n`: 1. Try every split `x + (i - x)`. 2. Compare: 1. `x * (i - x)` 2. `x * dp[i - x]` 3. Store the best value in `dp[i]`. Return: ```python dp[n] ``` ## Walkthrough Use: ```text n = 10 ``` Some important values: ```text dp[2] = 1 from 1 + 1 dp[3] = 2 from 1 + 2 dp[4] = 4 from 2 + 2 dp[5] = 6 from 2 + 3 dp[6] = 9 from 3 + 3 dp[7] = 12 from 3 + 4 dp[8] = 18 from 3 + 3 + 2 dp[9] = 27 from 3 + 3 + 3 dp[10] = 36 from 3 + 3 + 4 ``` For `i = 10`, one split is: ```text 3 + 7 ``` If we do not break `7`, product is: ```text 3 * 7 = 21 ``` If we break `7` optimally: ```text dp[7] = 12 ``` then product is: ```text 3 * 12 = 36 ``` So `dp[10]` becomes `36`. ## Correctness The algorithm considers every possible first split of each integer `i`. For a fixed split: ```text i = x + (i - x) ``` there are exactly two relevant choices for the second part. It can remain whole, giving: ```text x * (i - x) ``` or it can be broken further, giving: ```text x * dp[i - x] ``` The value `dp[i - x]` is already correct because `i - x < i`, and the table is filled from smaller values to larger values. Taking the maximum over all first parts `x` therefore considers every valid way to break `i`. The base value handles the smallest subproblem. Since `dp[n]` is computed from all valid breaks of `n`, it equals the maximum product obtainable after breaking `n` into at least two positive integers. ## Complexity | Metric | Value | Why | |---|---|---| | Time | `O(n^2)` | For each `i`, we try up to `i - 1` splits | | Space | `O(n)` | The `dp` array stores one value for each integer | Given `n <= 58`, this is easily fast enough. ## Implementation ```python class Solution: def integerBreak(self, n: int) -> int: dp = [0] * (n + 1) dp[1] = 1 for total in range(2, n + 1): for first in range(1, total): rest = total - first dp[total] = max( dp[total], first * rest, first * dp[rest], ) return dp[n] ``` ## Code Explanation Create the DP table: ```python dp = [0] * (n + 1) ``` Set the smallest useful value: ```python dp[1] = 1 ``` Now compute products for each `total`: ```python for total in range(2, n + 1): ``` Try every possible first number: ```python for first in range(1, total): ``` The remaining number is: ```python rest = total - first ``` Then compare the two choices: ```python first * rest ``` means we stop splitting the remaining part. ```python first * dp[rest] ``` means we split the remaining part optimally. The best value is stored in: ```python dp[total] ``` ## Greedy Math Version There is also a shorter mathematical solution. For maximum product, we want to use as many `3`s as possible, except when the remainder would be `1`. Why? For values larger than `4`, splitting off a `3` improves or preserves the product. But a remainder of `1` is bad because: ```text 3 * 1 < 2 * 2 ``` So if the remainder is `1`, replace one `3 + 1` with `2 + 2`. Implementation: ```python class Solution: def integerBreak(self, n: int) -> int: if n == 2: return 1 if n == 3: return 2 product = 1 while n > 4: product *= 3 n -= 3 return product * n ``` This version runs in `O(n)` time with the loop, or `O(1)` if written with exponentiation. ## Testing ```python def run_tests(): s = Solution() assert s.integerBreak(2) == 1 assert s.integerBreak(3) == 2 assert s.integerBreak(4) == 4 assert s.integerBreak(5) == 6 assert s.integerBreak(6) == 9 assert s.integerBreak(10) == 36 assert s.integerBreak(12) == 81 assert s.integerBreak(58) == 1549681956 print("all tests passed") run_tests() ``` Test meaning: | Test | Why | |---|---| | `2` | Smallest input, must split into `1 + 1` | | `3` | Must split, so answer is `2`, not `3` | | `4` | Best split is `2 + 2` | | `5` | Best split is `2 + 3` | | `6` | Best split is `3 + 3` | | `10` | Standard sample | | `12` | All `3`s | | `58` | Upper constraint |