Problem Statement
A number n can be broken into three parts n/2, n/3, and n/4 (consider only the integer part). Each number obtained in this process can be divided further recursively. Find the maximum sum that can be obtained by summing up the divided parts together.
Note: Given number must be divided at least once.
Example 1
Input:
n = 12
Output: 13
Explanation: Break n = 12 in three parts
{12/2, 12/3, 12/4} = {6, 4, 3}, now current
sum is = (6 + 4 + 3) = 13. Further breaking 6,
4 and 3 into parts will produce sum less than
or equal to 6, 4 and 3 respectively.
Solution
//User function Template for Java
//recursive solution tc : o(3^n) as we are calling recursive function 3 times /2,/3 and /4
//space time complexity is : o(3^n) auxillary space for the stack as their will be
// 3^n stack space that will be required
/*
class Solution
{
public int maxSum(int n)
{
return solve(n);
}
public int solve(int n){
if(n==1 || n==0) return n;
int a = n/2;
int b = n/3;
int c = n/4;
return Integer.max(n,
solve(a)+solve(b)+solve(c)
);
}
} */
// optimized solution using dynamic programming memoization top down approach
// time complexity is O(n) as at max there will be n states and dp will traverse those states
// space complexity will be O(n) for dp and o(n) for stack space;
class Solution
{
public int maxSum(int n)
{
int dp[] = new int[1000001];
Arrays.fill(dp,-1);
return solve(n,dp);
}
public int solve(int n,int dp[]){
if(n==1 || n==0) return n;
if(dp[n]!=-1) return dp[n];
int a = n/2;
int b = n/3;
int c = n/4;
return dp[n]= Integer.max(n,
solve(a,dp)+solve(b,dp)+solve(c,dp)
);
}
}
Top comments (0)