Integer Break

The key idea

To maximize a product of parts that sum to n, every part should be a 3 (use a 2 only for the leftover). A factor of 1 is always wasteful, and any factor of 4 or more can be split further to grow the product, so 2s and 3s are the only pieces worth keeping.

Problem

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.

For example, you may write n as n = a + b + c + ... where each part is a positive integer, and your goal is to make a * b * c * ... as large as possible.

Constraints

2 <= n <= 58

Examples

Input: n = 2 Output: 1

Input: n = 8 Output: 18

Input: n = 10 Output: 36

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →