In 9:02, I believe there's an error. Since we're looking through elements in possible subsets of size 1, this means that B must equal 5, since this is the size of the other subset. Using the formula we would take 5 * 42 / 6 = 30, and since 30 isn't found in the first list, we continue. Recall that each row in the DP matrix represents sums of size A. Fortunately, you find the result is still true at A = 2, looking for sum of 4 * 42 / 6 = 24, and we find it. Great video regardless, you are AMAZING at explaining.
Thank you so much! One tip, if I may: the way you wrote it on the whiteboard: "only possible if sum * i % n == 0 for i from 1 to n - 1" suggests that the problem is only solvable if: FOR EVERY i --> the sentence "sum * i % n == 0" stands. I listened closely to what you said between 04:37 - 04:53 and this became clear, but I just thought it could be useful to point out. Thanks again! And God bless! Nice work!
Nice solution! But I do have trouble understanding the complexity of the most inner loop. Could you please explain more on it? Why it is bounded by 10^5n? Thank you!
Now that I understand more) Could you drop the previous sums before building the next one? Like: Can we do this with the partition of size 1? Nope - build partitions of size 2. Drop the previous ones?
It seems weird to me, that we sum up numbers this way: so we will also store sums of the same number several times. So we can store sum in "sums", which contains the same value several times. This "sum" may not be valid, but we can find it in a search loop, getting a false positive result.
if we have input 2,12,18,16,19,3. sum = 70. 70*3/6 = 35, so it is possible. When we will calculate a second level of our matrix, we will have there 16+3. When we will calculate third level of our matrix, we will add there 16 again, so we will get there 16+3+16 = 35. And so the algo will return true, when it is not correct.
nope, you have to check whether it is possible or not by multiplying by each element with sum and taking mod. lets say sum%n!= 0, but still there may be some case where sum*i%n==0. hope you get it.
In 9:02, I believe there's an error. Since we're looking through elements in possible subsets of size 1, this means that B must equal 5, since this is the size of the other subset. Using the formula we would take 5 * 42 / 6 = 30, and since 30 isn't found in the first list, we continue. Recall that each row in the DP matrix represents sums of size A. Fortunately, you find the result is still true at A = 2, looking for sum of 4 * 42 / 6 = 24, and we find it.
Great video regardless, you are AMAZING at explaining.
Thank you so much! One tip, if I may: the way you wrote it on the whiteboard: "only possible if sum * i % n == 0 for i from 1 to n - 1" suggests that the problem is only solvable if: FOR EVERY i --> the sentence "sum * i % n == 0" stands. I listened closely to what you said between 04:37 - 04:53 and this became clear, but I just thought it could be useful to point out. Thanks again! And God bless! Nice work!
nice men i don't think there is any youtube channel like this gd work
Nice solution! But I do have trouble understanding the complexity of the most inner loop. Could you please explain more on it? Why it is bounded by 10^5n? Thank you!
May I know why this loop [ for (int i = m; i >= 1; -- i) ] not going in the direction from 1 to ls.size() -1. Thanks.
End formula is {summation of Ai = B * sum % n} then why are we checking it against 0 ?
Please clarify.
Thanks.
summation of Ai must equal a whole number which implies our RHS must also be a whole number or in other words, B*sum % n must leave no remainder.
Now that I understand more) Could you drop the previous sums before building the next one?
Like: Can we do this with the partition of size 1? Nope - build partitions of size 2. Drop the previous ones?
yea, i think that would work. and it would be more efficient
Could you explain this a bit more, please.?
great work. surprised the views are so low.
It seems weird to me, that we sum up numbers this way: so we will also store sums of the same number several times. So we can store sum in "sums", which contains the same value several times. This "sum" may not be valid, but we can find it in a search loop, getting a false positive result.
if we have input 2,12,18,16,19,3. sum = 70. 70*3/6 = 35, so it is possible. When we will calculate a second level of our matrix, we will have there 16+3. When we will calculate third level of our matrix, we will add there 16 again, so we will get there 16+3+16 = 35. And so the algo will return true, when it is not correct.
Just Brilliant !!
In pruning, we can just check (sum%n), correct me if I'm Wrong.
nope, you have to check whether it is possible or not by multiplying by each element with sum and taking mod. lets say sum%n!= 0, but still there may be some case where sum*i%n==0. hope you get it.
Omg🔥..
Brilliant solution man..
Thank you ❤️🔥
can this be implemented in C ?
Interesting algorithm, thanks
This is not O(n^3) it's O(2^n)
God, everyone knows leetcode
Brilliant!
amazing
WOW
This is giving TLE.