Integer Break

Desicription

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example 1:

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

Example 2:

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

Note: You may assume that n is not less than 2 and not larger than 58.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int integerBreak(int n) {
if(n == 2) {
return 1;
} else if(n == 3) {
return 2;
}

int res = 1;
while(n > 4) {
res *= 3;
n -= 3;
}
return n * res;
}
};