Integer Break

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

GoogleAmazonMicrosoft

Problem Description

Given an integer n, break it into the sum of k positive integers, where k ≥ 2, and maximize the product of those integers.

Return the maximum product you can get.

Examples

Example 1:

Input: n = 2 Output: 1 Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: n = 10 Output: 36 Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Constraints

2 ≤ n ≤ 58

Why 3s Are Better Than 2s

Mathematically, breaking a number into factors of e ≈ 2.718 maximizes the product. Since we must use integers, we want factors as close to e as possible, which are 2 and 3. Since 3 * 3 > 2 * 2 * 2 (9 > 8), we should prioritize factors of 3 over 2 whenever possible.

Rules of 3:

If n = 2, return 1 (1 + 1).
If n = 3, return 2 (2 + 1).
For n > 3, keep dividing n by 3:
- If remainder is 0, the product is 3^(n/3).
- If remainder is 1, group one 3 with the remainder to form a 4 (since 3 * 1 < 2 * 2). Product is 3^((n/3) - 1) * 4.
- If remainder is 2, product is 3^(n/3) * 2.

Solution 1: Greedy Math (O(1))

class Solution {
    public int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;

        int numThrees = n / 3;
        int remainder = n % 3;

        if (remainder == 0) {
            return (int) Math.pow(3, numThrees);
        } else if (remainder == 1) {
            return (int) Math.pow(3, numThrees - 1) * 4;
        } else {
            return (int) Math.pow(3, numThrees) * 2;
        }
    }
}

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

        num_threes = n // 3
        remainder = n % 3

        if remainder == 0:
            return 3 ** num_threes
        elif remainder == 1:
            return (3 ** (num_threes - 1)) * 4
        else:
            return (3 ** num_threes) * 2

#include <cmath>

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

        int numThrees = n / 3;
        int remainder = n % 3;

        if (remainder == 0) {
            return std::pow(3, numThrees);
        } else if (remainder == 1) {
            return std::pow(3, numThrees - 1) * 4;
        } else {
            return std::pow(3, numThrees) * 2;
        }
    }
};

Complexity Analysis:

Time Complexity: O(log N) for power computation, effectively O(1).
Space Complexity: O(1).

Solution 2: 1D DP (O(N²))

Let dp[i] be the maximum product of partition values for integer i. dp[i] = max(j * (i - j), j * dp[i - j]) for all j from 1 to i / 2.

Here, j * (i - j) is the case where we split i into exactly two parts j and i - j, and j * dp[i - j] is the case where we split i - j further into more parts.

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[1] = 1

        for i in range(2, n + 1):
            for j in range(1, i):
                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])

        return dp[n]

#include <vector>
#include <algorithm>

class Solution {
public:
    int integerBreak(int n) {
        std::vector<int> dp(n + 1, 0);
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = std::max({dp[i], j * (i - j), j * dp[i - j]});
            }
        }
        return dp[n];
    }
};