Problem Explanation

The task here is to break a positive integer n into the sum of at least two positive integers, such that the product of these integers is as large as possible.

For example, if the input is 10, we can break it down to 3 + 3 + 4 where the product 3 * 3 * 4 gives 36 which is the largest possible product in this case.

A key insight to solve this problem is that we only need factors 1, 2, and 3 to obtain the maximum possible product. This is because any factor f >= 4 can be replaced with 2 and f - 2 without losing the optimality, as 2(f - 2) = 2f - 4 >= f. Therefore, we can say that we never need a factor of 4 or above. Also, 3 * 3 is better than 2 * 2 * 2, which means there's no need to use 2 more than twice.

Let's take an example to further understand the problem:

Input: 10

Our task is to break down 10 into 1, 2, and 3 (and combinations of these) and find the maximum product possible.

• We keep subtracting 3 from 10 until the result is less or equal to 4.

• On the first subtraction, we get 7 (10 - 3).

• On the second subtraction, we get 4 (7 - 3).

Now that the resulting number (4) is less than or equal to 4, we stop subtracting 3 and multiply 4 with the product of 3 and 3 we used during the subtractions.

Calculating the product gives:

1
2
33 * 3 * 4 = 36.

Hence, the maximum product you can get from 10 is 36.

Python Solution

1
2python
3class Solution:
4    def integerBreak(self, n: int) -> int:
5        if n == 2:
6            return 1
7        if n == 3:
8            return 2
9        
10        ans = 1
11        
12        while n > 4:
13            n -= 3
14            ans *= 3
15        ans *= n
16        return ans

Java Solution

1
2java
3class Solution {
4    public int integerBreak(int n) {
5        if (n == 2)
6            return 1;
7        if (n == 3)
8            return 2;
9        
10        int product = 1;
11        
12        while (n > 4) {
13            n -= 3;
14            product *= 3;
15        }
16        product *= n;
17        
18        return product;
19    }
20}

Javascript Solution

1
2javascript
3class Solution {
4    integerBreak(n) {
5        if (n === 2)
6            return 1;
7        if (n === 3)
8            return 2;
9        
10        let product = 1;
11        
12        while (n > 4) {
13            n -= 3;
14            product *= 3;
15        }
16        product *= n;
17        
18        return product;
19    }
20}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int integerBreak(int n) {
6        if (n == 2)
7            return 1;
8        if (n == 3)
9            return 2;
10
11        int product = 1;
12
13        while (n > 4) {
14            n -= 3;
15            product *= 3;
16        }
17        product *= n;
18
19        return product;
20    }
21};

C# Solution

1
2csharp
3public class Solution {
4    public int IntegerBreak(int n) {
5        if (n == 2)
6            return 1;
7        if (n == 3)
8            return 2;
9
10        int product = 1;
11
12        while (n > 4) {
13            n -= 3;
14            product *= 3;
15        }
16        product *= n;
17
18        return product;
19    }
20}

The complexity of this algorithm is O(1) since the loop runs a constant number of times for the given range of n (2 ≤ n ≤ 58).

Implementation Details

As explained above, the approach taken in all solutions is iterative, where the integer n is reduced by 3 in each loop until it becomes less than or equal to 4. The product variable is then updated by multiplying it with three in each iteration. After the loop, the remaining value of n is then used to update the product variable for the last time.

• The code starts by handling base cases for when n is 2 or 3, directly returning 1 or 2 respectively, because these are the maximum products for these inputs according to the problem constraints.
• A variable product is initialized at 1. This variable will hold our result, which is the maximum product we can get by breaking n into at least two positive integers.
• A while loop then repeatedly subtracts 3 from n and multiplies our product by 3, making sure that n never gets less than 4.
• Once n <= 4, the loop ends and product is multiplied once with n. n will be 4, 3, or 2 at this point because if n is 1, it doesn't change the value of product.
• Finally, the result is returned as the maximum product of integers that add up to the original input n.

By following this approach, we ensure that we maximize the product by breaking down the number into factors of 3 and 2. This leverages the mathematical property that for numbers >= 5, it's always more efficient to break down the number into a sum of threes rather than into other integers (if possible), to get a larger product.

Complexity Analysis

As for the time complexity, the while loop runs n/3 times, making the solution O(n). However, since the problem constraints limit n to 58, we can also say the time complexity is O(1); the function always runs for a constant time regardless of the input size.

The space complexity of this solution is O(1) as well, since no additional space that scales with the input size is used. It only uses a constant amount of space to store the variable product and n.