Given an integer n, find two or more integers such that their sum is equal to n, where the product of these integers is maximized, and return this product.
Constraints
n ≤ 100,000
Example 1
Input
n = 11
Output
54
Explanation
3 + 3 + 3 + 2 = 11 and 3 * 3 * 3 * 2 = 54
Maximize the Split Product (Integer Break) via Greedy Algorithm
Given number 6, we can split it into 3*3 which is the largest (other than 2*2*2, or 3*2*1, or 2*2*1*1). Therefore, we can greedily pick/split 3 until the number is smaller than 4 – then we multiply the remaining.
1 2 3 4 5 6 7 8 9 10 | int maxSplitProduct(int n) { if ((n == 1) or (n == 2)) return 1; if (n == 3) return 2; int ans = 1; while (n > 4) { n -= 3; ans *= 3; } return ans * n; } |
int maxSplitProduct(int n) {
if ((n == 1) or (n == 2)) return 1;
if (n == 3) return 2;
int ans = 1;
while (n > 4) {
n -= 3;
ans *= 3;
}
return ans * n;
}This can also be solved via Dynamic Programming – Integer Break. The time complexity is O(N) which is superior than Dynamic Programming Algorithm in this case.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
240 wordsloading...
Last Post: Teaching Kids Programming - Multipy Two Integers Without Multiplication, Division and Bit Shifting
Next Post: Using Breadth First Search Algorithm to Count the Number of Leaves and Internal Nodes in Binary Tree