343. Integer Break

Problem Link

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.

 

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.

 

Constraints:

• 2 <= n <= 58

Solution

---

Python3

class Solution:
    def integerBreak(self, n: int) -> int:
        # 2 -> 1
        # 3 -> (1, 2)
        # 4 -> 4
        # 5 -> (3, 2) better than (4, 1)
        # 6 -> (3, 3) better than (4, 2)
        # 7 -> (4, 3) better than (3, 3, 1)
        # 8 -> (3. 3. 2) better than (4, 3)
        # 9 -> (3, 3, 3) better than (5, 4)
 
        if n == 2: return 1
        if n == 3: return 2
        if n == 4: return 4
 
        res = 1
        while n > 4:
            res *= 3
            n -= 3
        
        res *= n
 
        return res

C++

class Solution {
public:
    int integerBreak(int n) {
        if(n==2)    return 1;
        if(n==3)    return 2;
        
        int res = 1;
        
        while (n > 4){
            res *= 3;
            n -= 3;
        }
            
        res *= n;
        
        return res;
    }
};