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.Solution in Python
Approach:
- Observations:
- When breaking a number into smaller parts, breaking it into numbers close to 3 generally gives the best product.
- The reason for this is mathematical: dividing a number into parts of 3 tends to maximize the product (since 3 is the most efficient number for maximizing the product when breaking down an integer).
- If a remainder is 1 when dividing by 3, it’s better to make one of the parts 4 instead of having 1, because 3 × 1 is less than 2 × 2.
- Key Strategy:
- If
n == 2orn == 3, we returnn - 1, because the maximum product we can get is1 * 1(forn = 2) or2 * 1(forn = 3). - For larger values of
n, we should keep dividingnby 3 until the remainder is either 2 or 4 (since these are the parts that give better products).
- If
- Steps to Solve:
- Handle base cases when
n <= 3. - For
n > 3, repeatedly subtract 3 fromnand multiply 3’s together. - If the remainder after dividing by 3 is 2, include the
2in the product; if the remainder is 1, handle it by adjusting the previous multiples of 3 (usually turn the last 3 into a 4).
- Handle base cases when
Python
class Solution:
def integerBreak(self, n: int) -> int:
# Base cases: For small values of n, return the best possible product
if n == 2:
return 1 # 1 + 1 = 2, 1 * 1 = 1
if n == 3:
return 2 # 2 + 1 = 3, 2 * 1 = 2
# Initialize product result
product = 1
# While n is greater than 4, keep subtracting 3 and multiplying the result by 3
while n > 4:
product *= 3
n -= 3
# At this point, n is either 2, 3, or 4, and we multiply it with the current product
product *= n
return productDetailed Explanation:
- Base Cases (
n = 2,n = 3):- If
n = 2, the only valid split is1 + 1, and the product is1 * 1 = 1. - If
n = 3, the valid split is2 + 1, and the product is2 * 1 = 2.
- If
- Loop for Larger Values (
n > 3):- For values of
ngreater than 4, we subtract 3 fromnand multiply the product by 3. This is because multiplying by 3 gives a better result than multiplying by any larger number. - We continue this until
nbecomes 4 or less.
- For values of
- Final Multiplication:
- After exiting the loop,
nwill be 2, 3, or 4, which should be multiplied directly to the accumulated product.
- After exiting the loop,
Solution in C++
C++
class Solution {
public:
int integerBreak(int n) {
// If n is 2 or 3, handle these edge cases directly
if (n == 2) return 1; // 2 = 1 + 1, 1 * 1 = 1
if (n == 3) return 2; // 3 = 1 + 2, 1 * 2 = 2
// Initialize the result variable which will store the maximum product
int product = 1;
// The idea is to split n into as many 3's as possible, since the number 3 maximizes the product.
// While n is greater than 4, keep subtracting 3 from n and multiply the product by 3.
while (n > 4) {
product *= 3;
n -= 3;
}
// When n is reduced to 4 or less, the remaining n should be multiplied to the product.
// This is because multiplying small numbers (like 2 or 4) will give better results than continuing to break them.
product *= n;
// Return the maximum product
return product;
}
};Solution in Javascript
JavaScript
var integerBreak = function(n) {
// Edge case: if n is 2, the only possible partition is 1 + 1.
if (n === 2) return 1;
// Edge case: if n is 3, the best partition is 2 + 1.
if (n === 3) return 2;
// We will try to break n into as many 3's as possible.
let product = 1;
// While n is greater than 4, subtract 3 from n and multiply the product by 3.
// We subtract 3 because the more 3's we have, the greater the product.
while (n > 4) {
product *= 3;
n -= 3;
}
// At this point, n is 2, 3, or 4.
// We multiply the remaining n with the product because breaking into smaller
// parts (like 1 + 1) would not yield a larger product.
product *= n;
return product;
};Solution in Java
Java
class Solution {
public int integerBreak(int n) {
// Base case: If n is 2, the only way to break it into two positive integers is 1+1.
// So, the maximum product in this case is 1 * 1 = 1.
if (n == 2) return 1;
// Base case: If n is 3, the only way to break it into two positive integers is 1+2.
// The maximum product in this case is 1 * 2 = 2.
if (n == 3) return 2;
// Initialize the product result
int product = 1;
// While n is greater than 4, keep reducing it by 3.
// This is because for any integer n >= 5, splitting it into (n-3) + 3
// results in a larger product compared to splitting into smaller numbers like 2 + (n-2).
while (n > 4) {
// Multiply the current product by 3 and reduce n by 3.
product *= 3;
n -= 3;
}
// After the loop, n will be either 2, 3, or 4.
// Multiply the remaining value of n to the product.
// n = 4 is directly 2*2, n = 3 or n = 2 will be already handled.
product *= n;
return product;
}
}