卖萌的弱渣

I am stupid, I am hungry.

Integer Break

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

given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note

you may assume that n is not less than 2.

Hint

There is a simple O(n) solution to this problem. You may check the breaking results of n ranging from 7 to 10 to discover the regularities.

Solution

  • Java 用所有的3作为因子，证明如下 思路
(Integer-Break.java) download
1
2
3
4
5
6
7
8
9
10
11
12

public class Solution {
    public int integerBreak(int n) {
        if (n==2) return 1;
        if (n==3) return 2;
        int product = 1;
        while (n>4){
            product *= 3;
            n -= 3;
        }
        return product*n;
    }
}
  • Python
(Integer-Break.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        ret = 1
        if n == 1 or n == 2:
            return ret
        if n== 3:
            return 2
        while n >= 2:
            # try 3 first
            if n % 3 ==0:
                n = n-3
                ret *= 3
            # if n%3 !=0 try 2
            elif n%2 ==0:
                n = n-2
                ret *=2
            else:
            # for others, use 3. Like 5 
                n = n-3
                ret *=3
        return ret