The reason your DP solution is slower than you expected is that you're doing double the work in your inner loop. Specifically, you can do `for i in range(1, num // 2):` instead of `for i in range(1, num):` because `for i in range(num // 2 + 1, num):` is essentially a repeat of the previous half.
Great explanation, although I preferred previous format - first explanation than code. I think the second loop could end earlier at num//2 + 1 because of symmetry.
No, this method is better so that we may have a clear image of each and every step of the code and the whole intuition of why we need what we did at each stage!
I dont agree. Please corect me if I am wrong Lets consider for n=8, Max product is = 2*3*3 = 18 But according to your approach it is Ceil(8/2)*2s = 2*2*2*2 = 16 which is less than optimal answer 18
Thank you for the solution !! It was very intuitive. I do have a question tho, if dp was an array rather than a dictionary it actually significantly slows down the time complexity. However, we are only obtaining the element so shouldn't the time of retrieval both be O(1) for both array and dictionary? Why the choice of dictionary?
The question says that input must be broken into the sum of k positive integers, where k >= 2. When you break up 4 into two pieces as (1, 3), it means that you select 1 as the first number and selecting 3 as the second number without breaking into pieces obeys the rule of k >= 2. However, if the actual input were 3, then you can not select 3 directly because k would be equal to 1 and it would break the rule of k >= 2. So, you can always select the number itself, if the number is not the actual input.
I actually am still finding it a little difficult to wrap my head around when input is n=2, and when the subproblem has n=2 i.e. why is dp[2]=2 ? i guess this is a very tricky edge case, i mean, I would have liked to handle it as a base case had the input number n =2, then i would return 1, but when 2 is a subproblem, then we would return 2 only and not 1. That part is a little confusing to me tbh.
I prefer the old style. Again, a bit of confusing problem and the way you explained is great as usual. I still didnt get it, need to watch couple more times.
dp[i] and dp[num-i] hold max values and they consist of at least one piece. For example, if the input were 8, dp will be {1 : 1, 2 : 2, 3 : 3, 4 : 4, 5 : 6, 6 : 9, 7 : 12, 8 : 18}. Here dp[8] = dp[6] * dp[2] = 18 -> dp[6] = dp[3] * dp[3] = 9 -> dp[3] = 3. So actually dp[8] is 3 * 3 * 2.
maxBreakProductOfNum = list(range(n+1)) maxBreakProductOfNum[n] = 0 for i in range(n+1): for j in range(i): maxBreakProductOfNum[i] = max(maxBreakProductOfNum[i], maxBreakProductOfNum[j]*maxBreakProductOfNum[i-j]) return maxBreakProductOfNum[n]
Not the most optimized solution. It can be solved in constant time. Just try to break n into 2 equal halves. The product of those numbers will be the max possible products. If n is even, for example, n=6, max product = n/2*n/2 i.e. 3*3 = 9 If n is odd, for example, n=5, max product = int(n/2)*int(n-n/2) i.e. 2*3 = 6
Let me know if you prefer drawing & code at the same time or separately!
Same time!
Doing it side by side gives an experience of how to do it in real interviews. Loved the video, Thanks for explanation!
same time
Same Time!
Same time
The reason your DP solution is slower than you expected is that you're doing double the work in your inner loop.
Specifically, you can do `for i in range(1, num // 2):` instead of `for i in range(1, num):` because `for i in range(num // 2 + 1, num):` is essentially a repeat of the previous half.
but then, there will be no overlapping subproblems right??
Brilliant
I'm so happy your chanel has sponsors💟
Prefer the drawing first!!
Great explanation, although I preferred previous format - first explanation than code. I think the second loop could end earlier at num//2 + 1 because of symmetry.
yeah i was thinking the same thing and searching if someone ask that😃
@@alonebeast5310 its actually not symmetry. As the numbers get larger, the sum is made up solely of 2s and 3s.
Amazing content as usual :) Could you please draw first to get a wider picture of a problem. First, we need to create a mental image then we can code.
No, this method is better so that we may have a clear image of each and every step of the code and the whole intuition of why we need what we did at each stage!
368: Largest Divisible Subset
For the inner for loop we can minimize the loop by only executing till num//2+1 to avoid duplicate calls / calculation .
There is a O(c) solution for this. Ceil(Num/2) × 2s (or 3×2s if remaining is odd)
I dont agree. Please corect me if I am wrong
Lets consider for n=8,
Max product is = 2*3*3 = 18
But according to your approach it is Ceil(8/2)*2s = 2*2*2*2 = 16 which is less than optimal answer 18
This is a really confusing problem, I think understanding what they want is the hardest part.
After doing a ton of CP with C++, it is pleasant to look at python code
Max product for a certain k would occur when the integers are as close to equal as possible
Thank you for the solution !! It was very intuitive.
I do have a question tho, if dp was an array rather than a dictionary it actually significantly slows down the time complexity. However, we are only obtaining the element so shouldn't the time of retrieval both be O(1) for both array and dictionary? Why the choice of dictionary?
if you implement with array you get collision error, but in dictionary you dont have to solve that
Thanks. I will init up to 3 😁
@NeetCode
4:05
why you can leave the 3 as it is? you must break it up into at least 2 elements. Or I'm wrong?
The question says that input must be broken into the sum of k positive integers, where k >= 2.
When you break up 4 into two pieces as (1, 3), it means that you select 1 as the first number and selecting 3 as the second number without breaking into pieces obeys the rule of k >= 2. However, if the actual input were 3, then you can not select 3 directly because k would be equal to 1 and it would break the rule of k >= 2. So, you can always select the number itself, if the number is not the actual input.
good explanation!!!@@berkeevrensevdi1788
Choices from [1,2,3,4,...,n-1] => coin change-esque?
I actually am still finding it a little difficult to wrap my head around when input is n=2, and when the subproblem has n=2 i.e. why is dp[2]=2 ? i guess this is a very tricky edge case, i mean, I would have liked to handle it as a base case had the input number n =2, then i would return 1, but when 2 is a subproblem, then we would return 2 only and not 1. That part is a little confusing to me tbh.
Please make more dynamic programming videos!!!! They are so good
Notification gang ✌
i saw the solution but i coded it in c++... so its not full cheating :)
I prefer the old style. Again, a bit of confusing problem and the way you explained is great as usual. I still didnt get it, need to watch couple more times.
Appreciate the feedback sir!
I know it's about coding, but I found a math solution that is easier to understand and to code.
Hello sir,I want help how can I learn logic for programming and I want learn python and I am self taught learner
Drawing first please. I like to understand stuff first and then code it afterwards on my own. I think its more helpful that way
but your code here only breaks an integer n into two pieces? val = dp[i] *dp[num-i]? what if the optimal break has more than 2 pieces
dp[i] and dp[num-i] hold max values and they consist of at least one piece.
For example, if the input were 8, dp will be {1 : 1, 2 : 2, 3 : 3, 4 : 4, 5 : 6, 6 : 9, 7 : 12, 8 : 18}. Here dp[8] = dp[6] * dp[2] = 18 -> dp[6] = dp[3] * dp[3] = 9 -> dp[3] = 3.
So actually dp[8] is 3 * 3 * 2.
How do you join the discord server
Can join here: discord.gg/ddjKRXPqtk
There is just no way to figure out the true DP solution directly. This problem is hard.
def integerBreak(self, n: int) -> int:
maxBreakProductOfNum = list(range(n+1))
maxBreakProductOfNum[n] = 0
for i in range(n+1):
for j in range(i):
maxBreakProductOfNum[i] = max(maxBreakProductOfNum[i], maxBreakProductOfNum[j]*maxBreakProductOfNum[i-j])
return maxBreakProductOfNum[n]
this gives wrong answer for n == 2 and n == 3, as for 2, 1*1 = 1 and for 3 , 1*2 = 2 but for all other cases it works
Not the most optimized solution. It can be solved in constant time.
Just try to break n into 2 equal halves. The product of those numbers will be the max possible products.
If n is even, for example, n=6, max product = n/2*n/2 i.e. 3*3 = 9
If n is odd, for example, n=5, max product = int(n/2)*int(n-n/2) i.e. 2*3 = 6
I don't agree. Let's say, If n is even, for example, n=8, n/2*n/2 i.e. 4*4 = 16 which is not equal to 18 (max product for 8).
First 😎