Leetcode Integer Break problem solution

YASH PAL,

In this Leetcode Integer Break problem solution you have 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.

Leetcode Integer Break problem solution

Problem solution in Python.

class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        if n == 2: return 1
        if n == 3: return 2
        if n == 4: return 4
        if n % 3 == 0: return 3**(n/3)
        if (n-4)%3 == 0:
            return 3**((n-4)/3)*4
        else:
            return 3**((n-2)/3)*2

Problem solution in Java.

class Solution {
    int[] dp;
    public int integerBreak(int n) {
        dp = new int[n+1];
        Arrays.fill(dp, -1);
        dp[0] = 1;
        return helper(n, 0);
    }
    
    public int helper(int n, int time)
    {
        if(dp[n]>0)return dp[n];
        int res = 0;
        for(int i = 1; i < n; i++)
        {
            res = Math.max(res, helper(n-i, time+1) * i);
        }
        
        if(time>=1){
            res = Math.max(res, n);
        }
        
        dp[n] = res;
        return res;
    }
}

Problem solution in C++.

class Solution {
public:
    map<int,int>mp;    
    int integerBreak(int n) {
        mp[1]=1;   
        if(mp.find(n)!=mp.end())
            return mp[n];
        int mx=INT_MIN;
        for(int i=1;i<=n/2;i++)
            mx=max(mx,max(i,integerBreak(i))*max(n-i,integerBreak(n-i)));
        mp[n]=mx;
        return mx;
    }
};

Problem solution in C.

#define MAX(N,M) (N > M ? N : M)
int my_integerBreak(int n, int *dp) {
    if (n <= 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    
    if (n == 3) {
        return 3;
    }
    
    if (dp[n] == -1) {
        dp[n] = MAX( 2 * my_integerBreak(n-2, dp), 3 * my_integerBreak(n-3, dp));    
    }
    
    return dp[n];
}

int integerBreak(int n){ 
    
    if (n <=1 ) {
        return 1;
    }
    
    if (n == 2) {
        return 1;
    }
    
    if (n == 3) {
        return 2;
    }
    
    int *dp = (int *)malloc(sizeof(int) * (n+1));
    memset(dp, -1, sizeof(int) * (n + 1));
    
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
    return MAX (2*my_integerBreak(n-2, dp), 3*my_integerBreak(n-3, dp));
}

coding problems