Integer Break

How it works

We can compute the result directly using the count of 3s. If n % 3 == 0, the answer is 3^(n/3). If n % 3 == 1, we should use one fewer 3 and multiply by 4 instead (since 2 * 2 > 3 * 1). If n % 3 == 2, we multiply the power of 3 by 2.

Steps

1. If n <= 3, return n - 1.
2. Compute res = 3^(n / 3).
3. If n % 3 == 1, return (res / 3) * 4.
4. If n % 3 == 0, return res.
5. Otherwise, return res * 2.

Complexity

• Time complexity: O(log n)
• Space complexity: O(1)

Things to watch for

Forgetting the Original Number Must Be Broken

A common mistake is allowing the original input n to remain unbroken. The problem requires at least one split, so returning n itself is invalid. For example, integerBreak(4) must return 4 (from 2 * 2), not 4 unchanged. Ensure your base case or initialization forces at least one break for the original number while still allowing subproblems to use values directly.

Mishandling Small Values of n

The cases n = 2 and n = 3 are special because breaking them actually produces a smaller product than keeping them whole (for subproblems). For n = 2, breaking gives 1 * 1 = 1 but we must return 1 since we must break. For n = 3, breaking gives at best 1 * 2 = 2. Many solutions fail by not treating these edge cases differently from the general recursive case.

Using Factors of 1 or Factors Greater Than 4

Breaking off a factor of 1 never helps since 1 * (n-1) < n. Similarly, keeping any factor greater than 4 is suboptimal because it can always be split into smaller factors with a larger product. For example, 5 should be split into 2 + 3 giving 6 rather than kept as 5. The optimal solution primarily uses factors of 2 and 3.

class Solution:
    def integerBreak(self, n: int) -> int:
        if n <= 3:
            return n - 1

        res = 3 ** (n // 3)
        if n % 3 == 1:
            return (res // 3) * 4

        return res * max(1, (n % 3))

class Solution {
public:
    int integerBreak(int n) {
        if (n <= 3) {
            return n - 1;
        }

        int res = pow(3, n / 3);
        if (n % 3 == 1) {
            return (res / 3) * 4;
        }

        return res * max(1, n % 3);
    }
};