Leetcode 343. Integer Break
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
from10
until the result is less or equal to4
. -
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
is2
or3
, directly returning1
or2
respectively, because these are the maximum products for these inputs according to the problem constraints. - A variable
product
is initialized at1
. This variable will hold our result, which is the maximum product we can get by breakingn
into at least two positive integers. - A while loop then repeatedly subtracts
3
fromn
and multiplies our product by3
, making sure thatn
never gets less than4
. - Once
n <= 4
, the loop ends andproduct
is multiplied once withn
.n
will be4
,3
, or2
at this point because ifn
is1
, it doesn't change the value ofproduct
. - 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
.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.