Last Updated: 14 Apr, 2021
Break The Integer
Moderate
Asked in companies
Ninja is given an integer ‘N’ . One day Ninja decides to break the integer into K positive parts (K>=2) such that the sum of all parts is equal to ‘N’.Ninja wants to maximize the product of all the ‘K’ parts.
Help Ninja in helping what maximum possible product it can obtain by breaking the integer ‘N’ into ‘K’ positive parts where ‘K’ can be any integer greater than 2.
Input Format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first and only line of the test case consists of a single integer ‘N’.
Output Format:
Return the maximum possible product Ninja can obtain by breaking integer ‘N’ into ‘K’ parts.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= ‘T’ <= 11
2 <= ‘N’ <= 55
Time Limit: 1 sec
Approaches
The main idea is to break the given integer ‘N’ into all possible ways and out of all possible ways the one with the maximum product will be the answer.
Algorithm:
- Create a recursive function calculate(int N,int ch=0).
- The base case for the function should be if N==0 || N==1 return 1.
- Run a loop from i equal to 1 to N+(ch==1).
- The recursive call for the above function will be:-
- In the end, return ans.
In Approach 1 there are many overlapping sub-cases Hence we will apply memoization in Approach 1 to avoid calculating sub-problems many times.
In the above sub-tree, we are calculating 2 two times and 1 two times.So we will use memoization to avoid calculating same problems.
Algorithm:
- Create an auxiliary dp array of size N+1.
- Create a recursive function calculate(int N,int dp[],int ch=0).
- The base case for the function should be if N==0 || N==1 return 1.
- Add memoization condition if dp[N]!=-1 return dp[N].
- The recursive call will be:-
- In the end return dp[N]=ans.
The main idea is to use the observation when the given number is broken into 2 and 3’s will give a maximum answer. If n%3 == 0 it means that the given number is a multiple of 3 hence break it as the sum of 3’s so the answer for this case will be pow(3, N/3).When N%3 == 2 then it means the given number can be broken into a sum of 2 and N/3 3’s.So answer for this case will be 2 * pow(3, N/3).
When N%3 == 1 it means that the given number can be broken into the sum of 4 and N/3 - 1 3’s (N>=2) . 4 will give the maximum answer when broken into 2 2’s. Hence answer for this case will be 4* pow(3, N/3-1).
Algorithm:
- Consider the base case when N==3 return 2.When N==2 return 1.
- If N%3 == 0 return pow( 3, N/3).
- Else If N%3 == 1 return 4*pow(3,N/3-1).
- Else return 2 * pow(3,N/3).