title
DP 18. Count Partitions With Given Difference | Dp on Subsequences

description
Lecture Notes/C++/Java Codes: https://takeuforward.org/dynamic-programming/striver-dp-series-dynamic-programming-problems/ Problem Link: https://bit.ly/3r8mG5b Pre-req for this Series: https://www.youtube.com/watch?v=yVdKa8dnKiE&list=PLgUwDviBIf0rGlzIn_7rsaR2FQ5e6ZOL9 a Make sure to join our telegram group for discussions: https://linktr.ee/takeUforward Full Playlist: https://www.youtube.com/watch?v=FfXoiwwnxFw&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY In this video, we solve the problem of count partitions with given difference. This problem is the fifth problem on DP on Subsequences Pattern. Please watch DP 17 before watching this. If you have not yet checked our SDE sheet, you should definitely do it: https://takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems/ You can also get in touch with me at my social handles: https://linktr.ee/takeUforward

detail
{'title': 'DP 18. Count Partitions With Given Difference | Dp on Subsequences', 'heatmap': [{'end': 350.288, 'start': 329.729, 'weight': 0.727}, {'end': 389.961, 'start': 362.85, 'weight': 0.791}, {'end': 634.628, 'start': 603.726, 'weight': 0.733}, {'end': 866.119, 'start': 805.096, 'weight': 1}, {'end': 934.826, 'start': 884.667, 'weight': 0.708}, {'end': 963.489, 'start': 938.829, 'weight': 0.889}], 'summary': 'Covers handling array problems, refining base case and subsequence sum algorithms, and subset sum and dynamic programming optimization, addressing viewer comments, implementing subsequence sum algorithm, and optimizing dynamic programming, with an unexpected test case output of 4.', 'chapters': [{'end': 206.693, 'segs': [{'end': 120.469, 'src': 'embed', 'start': 0.33, 'weight': 3, 'content': [{'end': 3.343, 'text': 'Hey everyone, welcome back to Take It Forward, where we are trying to take you forward.', 'start': 0.33, 'duration': 3.013}, {'end': 13.966, 'text': "So dp 18 is what we will be doing today, but before that i'd love to address some of the comments that were there in the dp 17 video.", 'start': 3.805, 'duration': 10.161}, {'end': 17.007, 'text': 'what was dp 17 video?', 'start': 13.966, 'duration': 3.041}, {'end': 18.547, 'text': 'find the number of subsets.', 'start': 17.007, 'duration': 1.54}, {'end': 24.009, 'text': 'yes, find the number of subsets whose sum is equivalent to k.', 'start': 18.547, 'duration': 5.462}, {'end': 36.577, 'text': 'okay. and in that video, in that video, a lot of people were saying me striver, what if the array is given us to as 0, comma 0, comma 1 and the sum is one?', 'start': 24.009, 'duration': 12.568}, {'end': 39.021, 'text': 'your code will just give you the answer.', 'start': 36.577, 'duration': 2.444}, {'end': 40.383, 'text': 'as one subset.', 'start': 39.021, 'duration': 1.362}, {'end': 53.737, 'text': 'ideally it should have been four subsets, because 0, comma 1, where I consider this 0 and this 1, then 0, comma 1 where I consider the next 0,', 'start': 42.572, 'duration': 11.165}, {'end': 60.32, 'text': 'and next 1, 0, comma 0 where I consider both the zeros and 1 and then just the 1.', 'start': 53.737, 'duration': 6.583}, {'end': 63.042, 'text': 'so ideally the answer should have been 4.', 'start': 60.32, 'duration': 2.722}, {'end': 66.223, 'text': 'so how did the previous code pass?', 'start': 63.042, 'duration': 3.181}, {'end': 72.147, 'text': 'so if I just go back to the code of the number of subsets, If you carefully see in the test cases,', 'start': 66.223, 'duration': 5.924}, {'end': 75.15, 'text': "it's clearly written the numbers will be greater than or equal to 1..", 'start': 72.147, 'duration': 3.003}, {'end': 82.218, 'text': "That's why I did not consider that case because we were clearly told that there will be no cases where there will be zeros.", 'start': 75.15, 'duration': 7.068}, {'end': 84.12, 'text': 'That is the only reason it did pass.', 'start': 82.258, 'duration': 1.862}, {'end': 86.783, 'text': 'Now, how would you solve this problem?', 'start': 84.801, 'duration': 1.982}, {'end': 91.048, 'text': 'Imagine I just change the constraints to be equal to zero.', 'start': 86.943, 'duration': 4.105}, {'end': 95.756, 'text': 'like i say, all the array of elements will be greater than equal to zero.', 'start': 91.048, 'duration': 4.708}, {'end': 100.925, 'text': 'so in that case, how will you, uh, solve this particular problem is a big concern, right?', 'start': 95.756, 'duration': 5.169}, {'end': 101.726, 'text': 'so can i say this?', 'start': 100.925, 'duration': 0.801}, {'end': 107.001, 'text': 'can i say this that if it is zero, Does 0 alter the sum??', 'start': 101.726, 'duration': 5.275}, {'end': 112.565, 'text': 'No, because addition of 0 or removal of 0 will never alter the sum.', 'start': 107.842, 'duration': 4.723}, {'end': 114.266, 'text': 'The sum will still stay the same.', 'start': 112.625, 'duration': 1.641}, {'end': 120.469, 'text': 'So, that is the idea that we will take into consideration and we will compute the number of 0s.', 'start': 114.866, 'duration': 5.603}], 'summary': 'Addressing concerns about counting subsets whose sum is k, considering zero elements in the array, and modifying constraints for solving the problem.', 'duration': 120.139, 'max_score': 0.33, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg330.jpg'}, {'end': 206.693, 'src': 'embed', 'start': 147.504, 'weight': 0, 'content': [{'end': 148.785, 'text': "I'll get just the one.", 'start': 147.504, 'duration': 1.281}, {'end': 159.27, 'text': 'so if i can figure out how many ways i can represent the two zeros, how many ways i can represent the two zeros, then the answer will be there.', 'start': 149.605, 'duration': 9.665}, {'end': 161.471, 'text': 'so how many ways can you represent the two zeros?', 'start': 159.27, 'duration': 2.201}, {'end': 161.851, 'text': "it's two to.", 'start': 161.471, 'duration': 0.38}, {'end': 165.092, 'text': 'the power n comes from the algorithm power set.', 'start': 161.851, 'duration': 3.241}, {'end': 167.354, 'text': "so if you don't know this algorithm, please check it out.", 'start': 165.092, 'duration': 2.262}, {'end': 175.878, 'text': 'the number of ways in which you can represent uh numbers are two to the power n into the original answer, where the original answer was one.', 'start': 167.354, 'duration': 8.524}, {'end': 181.179, 'text': 'so 2 to the power 2 into 1 is 4 into 1 is 4 subsets.', 'start': 175.878, 'duration': 5.301}, {'end': 183.3, 'text': "so that's one of the ways you will solve it,", 'start': 181.179, 'duration': 2.121}, {'end': 194.062, 'text': "where you say that you're going to compute the power like the number of zeros and then you just do power 2 to the power n into whatever answer you're getting from the written test case.", 'start': 183.3, 'duration': 10.762}, {'end': 197.283, 'text': 'but the question is, how do you correct it?', 'start': 194.062, 'duration': 3.221}, {'end': 200.428, 'text': 'how do you correct it?', 'start': 197.283, 'duration': 3.145}, {'end': 203.63, 'text': 'because that is the biggest stuff that we have to understand.', 'start': 200.428, 'duration': 3.202}, {'end': 206.693, 'text': "So why did it fail? Let's go to the code.", 'start': 204.271, 'duration': 2.422}], 'summary': 'The algorithm calculates 2 to the power n to determine the number of ways to represent the two zeros.', 'duration': 59.189, 'max_score': 147.504, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg147504.jpg'}], 'start': 0.33, 'title': 'Handling array problems', 'summary': "Addresses viewer comments on finding subsets whose sum is equivalent to k, discusses the impact of adding zero constraints to an array problem, and explains the calculation of subsets with zeros, highlighting algorithm 'power set' and its application.", 'chapters': [{'end': 75.15, 'start': 0.33, 'title': 'Take it forward: dp 18 and addressing viewer comments', 'summary': "Addresses viewer comments on a previous video regarding finding subsets whose sum is equivalent to k, highlighting a scenario where the code did not produce the expected result, and explains the discrepancy by examining the code's condition for test cases.", 'duration': 74.82, 'highlights': ['The chapter addresses viewer comments on a previous video regarding finding subsets whose sum is equivalent to k.', 'The code in a previous video produced an unexpected result when given an array of 0, 0, 1 and a sum of one, resulting in only one subset instead of the expected four subsets.', "The code's condition for test cases states that the numbers will be greater than or equal to 1."]}, {'end': 120.469, 'start': 75.15, 'title': 'Handling zero constraints in array problem', 'summary': 'Discusses the impact of adding zero constraints to an array problem, emphasizing that the sum remains unchanged when zeros are added or removed, and poses a question on how to solve the problem under these conditions.', 'duration': 45.319, 'highlights': ['The sum remains unchanged when zeros are added or removed from the array, as the addition or removal of 0 does not alter the sum.', 'The concern is raised about solving the problem when the constraints are changed to include zeros in the array.', 'The speaker emphasizes that the problem of computing the number of zeros becomes a significant consideration when the constraints are altered to include zeros.']}, {'end': 206.693, 'start': 121.63, 'title': 'Counting subsets with zeros', 'summary': "Discusses the calculation of subsets with zeros, presenting the approach for representing two zeros and the number of resulting subsets, in turn demonstrating the use of the algorithm 'power set' and its application to solving the problem.", 'duration': 85.063, 'highlights': ["The number of ways to represent two zeros is 2^2, resulting in 4 subsets, as derived from the 'power set' algorithm.", 'The approach involves computing 2^n times the original answer, resulting in 4 subsets in this case.', "The algorithm 'power set' is utilized to determine the number of ways to represent the two zeros, resulting in 4 subsets.", 'Understanding the correction for the failed code is emphasized as a crucial aspect of the problem-solving process.']}], 'duration': 206.363, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg330.jpg', 'highlights': ["The number of ways to represent two zeros is 2^2, resulting in 4 subsets, as derived from the 'power set' algorithm.", "The algorithm 'power set' is utilized to determine the number of ways to represent the two zeros, resulting in 4 subsets.", 'The approach involves computing 2^n times the original answer, resulting in 4 subsets in this case.', 'The chapter addresses viewer comments on a previous video regarding finding subsets whose sum is equivalent to k.', 'Understanding the correction for the failed code is emphasized as a crucial aspect of the problem-solving process.', 'The sum remains unchanged when zeros are added or removed from the array, as the addition or removal of 0 does not alter the sum.', 'The concern is raised about solving the problem when the constraints are changed to include zeros in the array.', 'The speaker emphasizes that the problem of computing the number of zeros becomes a significant consideration when the constraints are altered to include zeros.', 'The code in a previous video produced an unexpected result when given an array of 0, 0, 1 and a sum of one, resulting in only one subset instead of the expected four subsets.', "The code's condition for test cases states that the numbers will be greater than or equal to 1."]}, {'end': 427.158, 'segs': [{'end': 306.991, 'src': 'embed', 'start': 275.849, 'weight': 1, 'content': [{'end': 281.353, 'text': "And I have to go deep till index equal to equal to 0, and that's when I think of the base case.", 'start': 275.849, 'duration': 5.504}, {'end': 283.195, 'text': "And that's when I think of the base case.", 'start': 281.934, 'duration': 1.261}, {'end': 285.497, 'text': "Now, what will be the base case? Let's think.", 'start': 283.775, 'duration': 1.722}, {'end': 293.885, 'text': 'if you are just standing at the index 0, that means just have a single element right and imagine if the sum is 0.', 'start': 286.641, 'duration': 7.244}, {'end': 297.547, 'text': 'if the sum is 0 and the element is 0, what options do you have?', 'start': 293.885, 'duration': 3.662}, {'end': 299.608, 'text': 'it will be like striver.', 'start': 297.547, 'duration': 2.061}, {'end': 306.991, 'text': 'either you can take this guy into your subsequence, because then also the sum will not be altered, or striver.', 'start': 299.608, 'duration': 7.383}], 'summary': 'Exploring base case at index 0, with single element and sum 0.', 'duration': 31.142, 'max_score': 275.849, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg275849.jpg'}, {'end': 355.529, 'src': 'heatmap', 'start': 319.56, 'weight': 0, 'content': [{'end': 324.025, 'text': 'so I can say if it is a zero and the sum is zero, I will have two options.', 'start': 319.56, 'duration': 4.465}, {'end': 327.107, 'text': "Either I'll take this zero or I'll not take this zero.", 'start': 324.665, 'duration': 2.442}, {'end': 329.169, 'text': 'So the first base case is very simple.', 'start': 327.487, 'duration': 1.682}, {'end': 336.874, 'text': 'If a sum is zero and an array of zero is also zero, then I can return a two.', 'start': 329.729, 'duration': 7.145}, {'end': 343.339, 'text': "That's the first base case because there can be two possible ways in which you can form the subsequence by taking it or by not taking it.", 'start': 337.114, 'duration': 6.225}, {'end': 345.521, 'text': "Let's think of the other case.", 'start': 343.839, 'duration': 1.682}, {'end': 350.288, 'text': "I'm at 0 and we have some 5 and the sum is 0.", 'start': 346.607, 'duration': 3.681}, {'end': 355.529, 'text': "so if you're looking at some 0 and if you decide to take this guy, then the sum will be altered.", 'start': 350.288, 'duration': 5.241}], 'summary': 'The algorithm deals with two possible cases involving zeros and sums, with two options and base cases for each scenario.', 'duration': 35.969, 'max_score': 319.56, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg319560.jpg'}, {'end': 387.92, 'src': 'embed', 'start': 362.85, 'weight': 3, 'content': [{'end': 370.852, 'text': "thereby I can say else if, or you can just write a if, because there's a written statement if sum is equal to 0, you return 1,", 'start': 362.85, 'duration': 8.002}, {'end': 372.652, 'text': "because there's only one way.", 'start': 370.852, 'duration': 1.8}, {'end': 377.926, 'text': "if this is 5 at the 0th index and the sum is 5, Then if I don't take it.", 'start': 372.652, 'duration': 5.274}, {'end': 380.052, 'text': 'Then the sum will not go to 0.', 'start': 378.046, 'duration': 2.006}, {'end': 380.553, 'text': 'Which is.', 'start': 380.052, 'duration': 0.501}, {'end': 384.224, 'text': "Problem Because it will not go if I don't take it.", 'start': 381.757, 'duration': 2.467}, {'end': 385.247, 'text': 'But if I take it.', 'start': 384.545, 'duration': 0.702}, {'end': 387.92, 'text': 'then minus 5 will happen and the sum will go to 0.', 'start': 385.899, 'duration': 2.021}], 'summary': 'Using if-else statements, return 1 if sum equals 0, else consider the impact of not taking the current value on the sum.', 'duration': 25.07, 'max_score': 362.85, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg362850.jpg'}, {'end': 389.961, 'src': 'heatmap', 'start': 362.85, 'weight': 0.791, 'content': [{'end': 370.852, 'text': "thereby I can say else if, or you can just write a if, because there's a written statement if sum is equal to 0, you return 1,", 'start': 362.85, 'duration': 8.002}, {'end': 372.652, 'text': "because there's only one way.", 'start': 370.852, 'duration': 1.8}, {'end': 377.926, 'text': "if this is 5 at the 0th index and the sum is 5, Then if I don't take it.", 'start': 372.652, 'duration': 5.274}, {'end': 380.052, 'text': 'Then the sum will not go to 0.', 'start': 378.046, 'duration': 2.006}, {'end': 380.553, 'text': 'Which is.', 'start': 380.052, 'duration': 0.501}, {'end': 384.224, 'text': "Problem Because it will not go if I don't take it.", 'start': 381.757, 'duration': 2.467}, {'end': 385.247, 'text': 'But if I take it.', 'start': 384.545, 'duration': 0.702}, {'end': 387.92, 'text': 'then minus 5 will happen and the sum will go to 0.', 'start': 385.899, 'duration': 2.021}, {'end': 389.961, 'text': 'So again, a single way.', 'start': 387.92, 'duration': 2.041}], 'summary': 'Explaining the logic of if-else statements and their impact on the sum, with a focus on returning 1 if the sum is equal to 0.', 'duration': 27.111, 'max_score': 362.85, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg362850.jpg'}, {'end': 446.065, 'src': 'embed', 'start': 414.295, 'weight': 4, 'content': [{'end': 414.715, 'text': "Let's check it out.", 'start': 414.295, 'duration': 0.42}, {'end': 416.595, 'text': 'So you see, the answer is now coming out to be 4,', 'start': 414.915, 'duration': 1.68}, {'end': 424.237, 'text': 'which they are not expecting because the code has been written like the tester has written the code in terms of numbers greater than equal to 1.', 'start': 416.595, 'duration': 7.642}, {'end': 427.158, 'text': 'thereby there is a problem, but you see the answer coming out to be true.', 'start': 424.237, 'duration': 2.921}, {'end': 435.84, 'text': "So that's the slight change that you will do in sum equal to like you have to just remove the sum equal to 0 and let it travel till the last index.", 'start': 427.418, 'duration': 8.422}, {'end': 437.56, 'text': 'Just let it travel till the last index.', 'start': 435.9, 'duration': 1.66}, {'end': 440.341, 'text': 'without actually stopping it in between.', 'start': 438.2, 'duration': 2.141}, {'end': 442.062, 'text': "So that's the minor change that you'll do.", 'start': 440.361, 'duration': 1.701}, {'end': 443.443, 'text': 'So enough of DP-17.', 'start': 442.223, 'duration': 1.22}, {'end': 446.065, 'text': "Now let's come back to the original stuff, which is DP-18.", 'start': 443.583, 'duration': 2.482}], 'summary': 'Tester found issue in code, fixed by removing condition, resulting in true answer.', 'duration': 31.77, 'max_score': 414.295, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg414295.jpg'}], 'start': 207.033, 'title': 'Refining base case and subsequence sum algorithm', 'summary': 'Discusses revising the base case and code to address problems, emphasizing considering all scenarios. it also covers the implementation of a subsequence sum algorithm, including base cases and an unexpected test case output of 4.', 'chapters': [{'end': 299.608, 'start': 207.033, 'title': 'Finding base case and going deep in code', 'summary': "Discusses the need to revise the base case and go deeper into the code to address problems arising from conditions like 'if sum equals 0' and emphasizes on the importance of considering all possible scenarios, ultimately leading to a reevaluation of the base case and recursive approach.", 'duration': 92.575, 'highlights': ["The need to revise the base case and go deeper into the code to address problems arising from conditions like 'if sum equals 0'.", 'Emphasizing on the importance of considering all possible scenarios and reevaluating the base case and recursive approach.', "The code's initial condition 'if sum is equal to, equal to 0' creating a problem and the decision to remove it.", 'The necessity to go deep till index is equal to 0 and the subsequent consideration of the base case and recursive approach.', 'The significance of considering all possible scenarios and reevaluating the base case and recursive approach.']}, {'end': 427.158, 'start': 299.608, 'title': 'Subsequence sum algorithm', 'summary': 'Discusses the implementation of a subsequence sum algorithm, covering base cases for sum and array elements, with the code outputting an unexpected result of 4 for a test case.', 'duration': 127.55, 'highlights': ['The algorithm addresses base cases for sum and array elements, returning 2 if both are zero, 1 if sum is zero and array element is non-zero, and 0 for all other cases.', "The test case output is 4, contrary to expectations, indicating potential issues with the code's handling of numbers greater than or equal to 1."]}], 'duration': 220.125, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg207033.jpg', 'highlights': ['The algorithm addresses base cases for sum and array elements, returning 2 if both are zero, 1 if sum is zero and array element is non-zero, and 0 for all other cases.', "The need to revise the base case and go deeper into the code to address problems arising from conditions like 'if sum equals 0'.", 'Emphasizing on the importance of considering all possible scenarios and reevaluating the base case and recursive approach.', "The code's initial condition 'if sum is equal to, equal to 0' creating a problem and the decision to remove it.", "The test case output is 4, contrary to expectations, indicating potential issues with the code's handling of numbers greater than or equal to 1."]}, {'end': 1070.017, 'segs': [{'end': 525.204, 'src': 'embed', 'start': 473.407, 'weight': 0, 'content': [{'end': 483.595, 'text': 'D count the number of partitions in which S1 is greater than than or equal to s2 and the difference between s1 and s2 is equal to d.', 'start': 473.407, 'duration': 10.188}, {'end': 487.436, 'text': 'so basically, if i understand the question properly, there is an array given.', 'start': 483.595, 'duration': 3.841}, {'end': 495.48, 'text': 'you have, to, uh, basically divide them into two parts, such that this part is giving you an s1 which is greater than equal to s2,', 'start': 487.436, 'duration': 8.044}, {'end': 498.841, 'text': 'and the difference between s1 and minus s2 should be equal to d.', 'start': 495.48, 'duration': 3.361}, {'end': 506.675, 'text': 'And you have to count how many different subsets can you divide them into such that this is true?', 'start': 500.512, 'duration': 6.163}, {'end': 510.157, 'text': "So, let's take one of the examples, something like 5, 2, 6, 4.", 'start': 506.975, 'duration': 3.182}, {'end': 517, 'text': 'So, if I take 5, 2, 6, 4, this is the array and the d is given as 3.', 'start': 510.157, 'duration': 6.843}, {'end': 525.204, 'text': 'So, if I take this, I can be like the two subsets will be 5, 2 and 6 and 4.', 'start': 517, 'duration': 8.204}], 'summary': 'Count the subsets where s1 >= s2 and s1 - s2 = d. example: array [5,2,6,4], d=3, subsets=2.', 'duration': 51.797, 'max_score': 473.407, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg473407.jpg'}, {'end': 634.628, 'src': 'heatmap', 'start': 603.726, 'weight': 0.733, 'content': [{'end': 613.073, 'text': 'So can I say I am looking for subsets, yes, I am looking for subsets which are having, yes, which are having.', 'start': 603.726, 'duration': 9.347}, {'end': 618.721, 'text': 'summation as total sum minus d by 2.', 'start': 614.176, 'duration': 4.545}, {'end': 621.884, 'text': 'so the question boils down to count.', 'start': 618.721, 'duration': 3.163}, {'end': 634.628, 'text': 'find the count of subsets whose sum is total sum minus the difference by 2, and this is nothing but dp 17.', 'start': 621.884, 'duration': 12.744}], 'summary': 'Looking for subsets with summation as total sum minus d by 2, for a total of dp 17.', 'duration': 30.902, 'max_score': 603.726, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg603726.jpg'}, {'end': 697.298, 'src': 'embed', 'start': 665.15, 'weight': 3, 'content': [{'end': 672.178, 'text': "That's one of the cases that total sum minus d has to be greater than zero.", 'start': 665.15, 'duration': 7.028}, {'end': 678.716, 'text': "Why?? Because if I'm looking for a sum, that's what is the sum.", 'start': 672.759, 'duration': 5.957}, {'end': 682.801, 'text': 'this sum is sum of a subset.', 'start': 678.716, 'duration': 4.085}, {'end': 689.629, 'text': "so if it's a subset and the numbers are greater than 0, how can a sum of a subset be negative?", 'start': 682.801, 'duration': 6.828}, {'end': 693.194, 'text': 'thereby this element has to be greater than 0..', 'start': 689.629, 'duration': 3.565}, {'end': 697.298, 'text': "you're dividing by 2 So again, there is no fractions.", 'start': 693.194, 'duration': 4.104}], 'summary': 'Total sum minus d must be > 0 for subset sum to be positive', 'duration': 32.148, 'max_score': 665.15, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg665150.jpg'}, {'end': 758.313, 'src': 'embed', 'start': 723.573, 'weight': 5, 'content': [{'end': 726.695, 'text': "and it has to be even, because you don't have decimals.", 'start': 723.573, 'duration': 3.122}, {'end': 732.499, 'text': 'so just check for these couple of cases and then the question boils down to count of subsets.', 'start': 726.695, 'duration': 5.804}, {'end': 735.1, 'text': 'yes, that is what the question boils down to.', 'start': 732.499, 'duration': 2.601}, {'end': 739.103, 'text': 'So we need the number of subsets, concept right?', 'start': 736.241, 'duration': 2.862}, {'end': 746.347, 'text': 'So just copy paste the entire changed code that we wrote for zeros and now we will paste it over here right?', 'start': 739.403, 'duration': 6.944}, {'end': 749.929, 'text': 'And over here can I say this that we require the total sum.', 'start': 747.007, 'duration': 2.922}, {'end': 758.313, 'text': "So, that's zero and then we can easily go across the array and we can add total sum plus equal to id.", 'start': 750.549, 'duration': 7.764}], 'summary': 'The question involves counting even subsets and pasting changed code to calculate total sum.', 'duration': 34.74, 'max_score': 723.573, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg723573.jpg'}, {'end': 866.119, 'src': 'heatmap', 'start': 799.294, 'weight': 2, 'content': [{'end': 805.096, 'text': 'but over here they have asked, since the answer may be too large, you have to return module of 10 to the power 9 plus 7.', 'start': 799.294, 'duration': 5.802}, {'end': 817.94, 'text': 'so really you can just declare a mod equal to 189 plus 7 and over here just make sure you give a mod.', 'start': 805.096, 'duration': 12.844}, {'end': 819.921, 'text': "that should be fine, let's.", 'start': 817.94, 'duration': 1.981}, {'end': 821.482, 'text': 'so, that was about the memory action.', 'start': 819.921, 'duration': 1.561}, {'end': 823.122, 'text': 'but how can we optimize this?', 'start': 821.482, 'duration': 1.64}, {'end': 824.983, 'text': 'obviously we can write tabulation.', 'start': 823.122, 'duration': 1.861}, {'end': 828.684, 'text': "so what i'll do is i'll copy paste the tabulation that we wrote over here.", 'start': 824.983, 'duration': 3.701}, {'end': 836.828, 'text': 'but this is definitely not going to work because it it does not handles the case where we have, uh, zeros.', 'start': 828.684, 'duration': 8.144}, {'end': 838.089, 'text': 'so what did we changed?', 'start': 836.828, 'duration': 1.261}, {'end': 840.491, 'text': 'if you remember, we removed sum of zero.', 'start': 838.089, 'duration': 2.402}, {'end': 844.993, 'text': 'so please remove sum of zero, because this was sum of zero at every index.', 'start': 840.491, 'duration': 4.502}, {'end': 850.957, 'text': "so we remove this first case, this, let's let's think about this.", 'start': 844.993, 'duration': 5.964}, {'end': 853.098, 'text': "afterwards let's write the other cases.", 'start': 850.957, 'duration': 2.141}, {'end': 866.119, 'text': "what's the first case if sum is zero and the number is zero at index zero, so if the number is zero And then dp of 0 at 0 will be 2..", 'start': 853.098, 'duration': 13.021}], 'summary': 'Optimizing tabulation for handling zero cases in memory action', 'duration': 25.689, 'max_score': 799.294, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg799294.jpg'}, {'end': 934.826, 'src': 'heatmap', 'start': 884.667, 'weight': 0.708, 'content': [{'end': 893.168, 'text': "Or else, if I'm at index 0, And the sum is 0, but the number is not 0.", 'start': 884.667, 'duration': 8.501}, {'end': 895.088, 'text': 'And there is only one way, which is not take.', 'start': 893.168, 'duration': 1.92}, {'end': 895.908, 'text': 'So there will be one case.', 'start': 895.168, 'duration': 0.74}, {'end': 900.01, 'text': 'What about this case? Number 0 less than or equal to target.', 'start': 896.569, 'duration': 3.441}, {'end': 906.651, 'text': 'Because at the 0th index, there can be a number, assume 5, and the target is also 5.', 'start': 900.81, 'duration': 5.841}, {'end': 907.672, 'text': 'So there is only one way.', 'start': 906.651, 'duration': 1.021}, {'end': 910.072, 'text': 'So you might think this is correct, but this will fail.', 'start': 908.032, 'duration': 2.04}, {'end': 918.555, 'text': 'What if number of 0 is 1, 0 only? Then it should have been, it will come as dp of 0 of 0 as 1, which is wrong.', 'start': 910.653, 'duration': 7.902}, {'end': 923.478, 'text': 'So, make sure the number of 0 is not equal to 0.', 'start': 919.295, 'duration': 4.183}, {'end': 928.582, 'text': 'In that case, anywhere, anywhere, I explain the case of 5.', 'start': 923.478, 'duration': 5.104}, {'end': 934.826, 'text': "If it contains 5, then it will just have one way, right? So, you just write at 5, there's only one way.", 'start': 928.582, 'duration': 6.244}], 'summary': 'Exploration of scenarios for zero and non-zero numbers in a dynamic programming context.', 'duration': 50.159, 'max_score': 884.667, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg884667.jpg'}, {'end': 986.011, 'src': 'heatmap', 'start': 938.829, 'weight': 4, 'content': [{'end': 939.97, 'text': 'So, this is the two ways.', 'start': 938.829, 'duration': 1.141}, {'end': 947.115, 'text': "If it is not having 0, it is having other numbers like 7, then there's only one way in which you can make the sum 0.", 'start': 940.49, 'duration': 6.625}, {'end': 948.736, 'text': "Those cases is what I've written over here.", 'start': 947.115, 'duration': 1.621}, {'end': 953.82, 'text': 'So, if you just now try to submit it, this is definitely going to run fine.', 'start': 949.256, 'duration': 4.564}, {'end': 956.703, 'text': "So, let's submit this.", 'start': 954.501, 'duration': 2.202}, {'end': 958.885, 'text': 'It does run.', 'start': 958.364, 'duration': 0.521}, {'end': 963.489, 'text': 'And if I submit this, it will definitely give me an accepted answer.', 'start': 960.286, 'duration': 3.203}, {'end': 968.653, 'text': "So, what's the next step? Why did it give us a wrong answer? Oh, we forgot to apply Modulo to it.", 'start': 963.949, 'duration': 4.704}, {'end': 970.455, 'text': 'So, please apply Modulo to it.', 'start': 969.114, 'duration': 1.341}, {'end': 971.856, 'text': 'Very important concept.', 'start': 970.935, 'duration': 0.921}, {'end': 975.759, 'text': 'Please make sure you apply Modulo to it every time you submit.', 'start': 973.217, 'duration': 2.542}, {'end': 981.145, 'text': 'So, after applying modulo, I will be submitting this and this should definitely be working fine.', 'start': 976.84, 'duration': 4.305}, {'end': 986.011, 'text': 'So, what is the next step? The next step is definitely space optimization.', 'start': 981.526, 'duration': 4.485}], 'summary': 'Using modulo ensures the expected outcome; space optimization is the next step.', 'duration': 47.182, 'max_score': 938.829, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg938829.jpg'}], 'start': 427.418, 'title': 'Subset sum and dynamic programming optimization', 'summary': 'Covers partitioning an array into two subsets with a given difference, exploring edge cases in the subset sum problem, and optimizing dynamic programming using tabulation and space optimization. it exemplifies the approach through specific examples and problem-solving techniques.', 'chapters': [{'end': 642.912, 'start': 427.418, 'title': 'Dp-18: partitions with given difference', 'summary': 'Discusses the problem of partitioning an array into two subsets such that their union is the original array, and then counting the number of partitions in which s1 is greater than or equal to s2, and the difference between s1 and s2 is equal to d, exemplified through an array of [5, 2, 6, 4] with d=3. it also explores the approach of finding the count of subsets whose sum is total sum minus the difference by 2, akin to the concept of dp 17 with a modified target.', 'duration': 215.494, 'highlights': ['The problem involves partitioning an array into two subsets and counting the number of partitions where S1 is greater than or equal to S2, and the difference between S1 and S2 is equal to d.', 'Illustrates an example with the array [5, 2, 6, 4] and d=3, showcasing the formation of subsets with their respective sums and the resulting difference.', 'Discusses the concept of finding the count of subsets whose sum is total sum minus the difference by 2, which is analogous to the concept of DP 17 with a modified target.']}, {'end': 799.294, 'start': 642.912, 'title': 'Edge cases in subset sum problem', 'summary': 'Discusses the edge cases in the subset sum problem, emphasizing that the total sum minus d has to be greater than zero and even, leading to the need to find the count of subsets.', 'duration': 156.382, 'highlights': ['The total sum minus d has to be greater than zero, as all numbers are greater than or equal to zero, ensuring the sum is positive.', 'The total sum minus d has to be even, as all numbers are integers and do not have decimals, necessitating the count of subsets to be found.', 'The question ultimately boils down to counting the number of subsets, requiring the use of the concept of the total sum and the target sum.']}, {'end': 1070.017, 'start': 799.294, 'title': 'Dynamic programming optimization', 'summary': 'Discusses optimizing dynamic programming using tabulation and space optimization, addressing cases of zeros and applying modulo, resulting in an accepted answer for the problem.', 'duration': 270.723, 'highlights': ['The chapter explains the process of optimizing dynamic programming using tabulation and addressing cases of zeros, ensuring that the solution runs fine and gives an accepted answer.', 'It emphasizes the importance of applying modulo to the solution every time it is submitted, which is crucial for obtaining the correct result.', 'The chapter also covers space optimization by omitting unnecessary rows and using a single row for the vector, effectively reducing space complexity and solving the problem using memation and tabulation.']}], 'duration': 642.599, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/zoilQD1kYSg/pics/zoilQD1kYSg427418.jpg', 'highlights': ['The problem involves partitioning an array into two subsets with S1 >= S2 and S1 - S2 = d', 'Illustrates an example with the array [5, 2, 6, 4] and d=3, showcasing the formation of subsets', 'The chapter explains the process of optimizing dynamic programming using tabulation', 'The total sum minus d has to be greater than zero, ensuring the sum is positive', 'Emphasizes the importance of applying modulo to the solution every time it is submitted', 'The question ultimately boils down to counting the number of subsets']}], 'highlights': ["The algorithm 'power set' is utilized to determine the number of ways to represent the two zeros, resulting in 4 subsets.", "The number of ways to represent two zeros is 2^2, resulting in 4 subsets, as derived from the 'power set' algorithm.", 'The approach involves computing 2^n times the original answer, resulting in 4 subsets in this case.', 'The problem involves partitioning an array into two subsets with S1 >= S2 and S1 - S2 = d.', 'The chapter explains the process of optimizing dynamic programming using tabulation.', 'Understanding the correction for the failed code is emphasized as a crucial aspect of the problem-solving process.', 'The sum remains unchanged when zeros are added or removed from the array, as the addition or removal of 0 does not alter the sum.', "The code's initial condition 'if sum is equal to, equal to 0' creating a problem and the decision to remove it.", "The need to revise the base case and go deeper into the code to address problems arising from conditions like 'if sum equals 0'.", 'The code in a previous video produced an unexpected result when given an array of 0, 0, 1 and a sum of one, resulting in only one subset instead of the expected four subsets.']}