Integer Break | Tree Diagram | Recursion | Memoization | AMAZON | Leetcode - 343

This is the 66th Video on our Dynamic Programming (DP) Playlist.
In this video we will try to solve a very good DP Problem - Integer Break (Leetcode-343).
I will be uploading another video explaining the Bottom Up version of this problem.

Trust me, this will no longer be a Medium Problem.
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Integer Break
Company Tags : AMAZON

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook

[dhairyachauhan]

I did it on my own thanks to you i am now good at making recursion diagrams and find solution from it :) .

[alokgautam]

thnx for this detailed soln, this was tricky somehow .

[dheerajpatwal]

did it on my own || thankyou for your consistent uploads :)

[saurabhtiwari]

I solved this question using greedy approach. But as usual ur outstanding in explaining 🎉🎉🎉.

I found a pattern where integer gets break down in pattern of 2 and 3's . That's how i imagine of a greedy solution

[jayantaggarwal]

sir, you are great... seriously, I was able to code and apply memo... own my own... my memo question got submitted in my first attempt 😍🤩

[ugcwithaddi]

I always get satisfied after watching literally any of your videos. Thanks a lot for making this super easy.

[DevOpskagyaan]

This channel has legendary and rare contents. Subscribed 🙌

[harsh.jain]

O(n) Approach using MATH :

int integerBreak(int n) {
int maxProd = 0;

for(int i=2; i<=n; i++){ // i<=n bcz we can only break n into n parts not more than that
int rem = n % i;
int div = n / i;

int curr_val = pow(div, i-rem) * pow(div+1, rem);

maxProd = max(maxProd, curr_val);
}

return maxProd;
}

After DRY RUN 3-4 examples we can get the pattern that we always get the max. product when n is divided into equal parts,

like :
at i=2 (breaking in 2 parts) n =10, 5*5 = 25 is max product
at i=2 (breaking in 2 parts) n =8, 4*4 = 16 is max product
at i=3 (breaking in 3 parts) n =9, 3*3*3 = 27 is max product

but above examples are only correct when remainder n%i == 0 i.e. (if n is completely divided in i parts)
but when remainder is not 0 then in that case :
we know we have to add the remainder in equal parts in (remainder no. of digits)

like at i=3 (breaking into 3 parts) n =10
rem = 10%3 = 1
div = 10/3 = 3

(3)^ (i-rem ) * (3+1)^(rem) = 3 * 3 *4 = 36 (this is the only possible max product for breaking 10 in 3 parts)


** Thanks MIK bhaiya, just bcz of you I am improving a lot daily **

[hollywoodedge]

instead of going from i=1 to i=n-1 we can just go from 1 to n/2 ; kyunki n/2 ke baad wo repeat hona chaalu ho jaata hai ... matlab 5 ko lelo, to 5 mai (1, 4) (2, 3) tak lelo to chalega kyunki (3, 2) bhi to wahi result dega jo (2, 3) deta.

[ssubhendu]

congrats ❤!! our stories reached to 10k coder 🔥✌️

[shreyyyc]

Congratulations bhai for hitting 10k subs. Wish you the best.

[Ramneet]

Done ✅ i got stuck when i was coding but did watch and able to do. Now i can say i can do these type of questions.

[HealthyOm]

always something specials for us in each vedios love keeep doing dont dont dont dont stop at at at any any any any movements ur only our hopes for fear of coding love love love love love love u from heart

[anuppatankar]

Congratulations for 10k subscribers 🎉🤝🏻

[sauravchandra]

Was able to solve it on my own. Thanks for making the concepts clear!

[nagmakhan]

Today I know how to make tree diagram just because of you. Thank you so much

[navinmishra]

class Solution {
public:
int integerBreak(int n) {
int ans = 0 ;

for(int k= 2 ; k <=n ;k++){
int num = n;
int prod = 1;
int parts = k ;
while(parts>0){
int a = num/parts;
prod *=a;
num -= a;
parts--;
}
ans = max(ans, prod);
}
return ans;
}
}; Time Complexity ->O(N*N/2), Aux Space - > O(1) Brute force class

DP Approach
Time Complexity -> O(N), Space -> O(N)
Solution {
public:
int integerBreak(int n) {
if (n <= 3) return n - 1;
vector<int> dp(n + 1);
dp[2] = 2;
dp[3] = 3;
for (int i = 4; i <= n; i++) {
dp[i] = max(2 * dp[i - 2], 3 * dp[i - 3]);
}

return dp[n];
}
};

[balakrishnanr]

do todays LC Ques too. Its HARD.

Ur way of explanation is good. keep it up

[nikhilbande]

Without Recursion and DP
if(n == 2 || n == 3)
{
return n-1;
}

int mid = n/2;

int final_call = INT_MIN;

while(mid >= 2)
{
int temp = n;
int ans =1;

while(temp > 0)
{
ans = ans * mid;
temp = temp - mid;

if(temp < mid +2)
{
break;
}
}

ans = ans*temp;

final_call = max(final_call, ans);

mid--;
}

return final_call;

[tosifkankod]

bro thanks and well explained and subscribed, one suggestion plz I think there's mic issue