# 343. Integer Break    • Time: $O(n / 3)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public: int integerBreak(int n) { // If an optimal product contains a factor f >= 4, then we can replace it // with 2 and f - 2 without losing optimality. As 2(f - 2) = 2f - 4 >= f, // we never need a factor >= 4, meaning we only need factors 1, 2, and 3 // (and 1 is wasteful). // Also, 3 * 3 is better than 2 * 2 * 2, so we never use 2 more than twice. if (n == 2) // 1 * 1 return 1; if (n == 3) // 1 * 2 return 2; int ans = 1; while (n > 4) { n -= 3; ans *= 3; } ans *= n; return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int integerBreak(int n) { // If an optimal product contains a factor f >= 4, then we can replace it // with 2 and f - 2 without losing optimality. As 2(f - 2) = 2f - 4 >= f, // we never need a factor >= 4, meaning we only need factors 1, 2, and 3 // (and 1 is wasteful). // Also, 3 * 3 is better than 2 * 2 * 2, so we never use 2 more than twice. if (n == 2) return 1; // 1 * 1 if (n == 3) return 2; // 1 * 2 int ans = 1; while (n > 4) { n -= 3; ans *= 3; } ans *= n; return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution: def integerBreak(self, n: int) -> int: if n == 2: return 1 if n == 3: return 2 ans = 1 while n > 4: n -= 3 ans *= 3 ans *= n return ans