275. Break for Best Product
A baker has n identical sugar cubes and must divide them into at least two piles, each pile containing a positive whole number of cubes, using every cube. The "sweetness score" of a division is the product of the pile sizes. For example, piles of sizes 2, 2 and 3 score 12.
Return the largest sweetness score that any valid division of n cubes can achieve. Because at least two piles are required, you cannot keep all the cubes together. The answer always fits in a 32-bit signed integer for the allowed range. A dynamic program over pile sizes works in O(n^2); a number-theoretic argument gives O(n) or even O(1) with a short loop.
Example 1
- Input:
- n = 13
- Output:
- 108
- Explanation:
Split 13 as 3+3+3+4 for a product of 108, which no other split beats.
Example 2
- Input:
- n = 29
- Output:
- 39366
- Explanation:
Nine threes and one two sum to 29 and multiply to 39366.
Example 3
- Input:
- n = 7
- Output:
- 12
- Explanation:
The best split of 7 is 3+4 (or 3+2+2), with product 12.
Constraints
2 ≤ n ≤ 58
The result is at most 318 * 4 = 1549681956, which fits in a signed 32-bit integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)