SUBARRAY SUMS DIVISIBLE BY K | LEETCODE 974 | PYTHON SOLUTION

Discord Link: / discord
Problem Link: leetcode.com/problems/subarra...
In this video we are solving an interesting question dealing with prefix sums: Subarray Sums Divisible by K (Leetcode 974).
This is really one of those questions where you've either solved enough prefix sum problems to understand how it works right away or you need to see the solution in order to get it. Figuring it out on your own is quite tricky as it's a bit hard to wrap your head around the logic with the remainders.

[@anishpatro9222]

Thank u so much... Now I properly understood prefix sum topic

[@firomsamt7642]

man this problem almost made me cry thank you for the explanation great video

[@crackfaang]

Glad you found it useful. I really hate all the problems that are like "divisible by K", "subarray sum equals K"... they're simple to code but hard to understand

[@firomsamt7642]

@@crackfaang yeah those questions that involve math and geometry are really hard to figure out

[@ivanzaplatar9033]

What helped me understand the motivation: Suppose we have two subarrays of sums, A, and B. Sum A has a remainder r and sum B doesn't have a remainder(divisible by k). We also know by the definition of divisibility that -- A = n1*k + r B = n2*k + 0 where n1 and n2 are some constants(not really important) adding them(pay attention to this part) A + B = n_1*k + r + n_2*k = (n_1 + n_2)*k + r WAIT THE REMAINDER IS THE SAME!! THIS HAS TO MEAN THAT ONE OF THEM DIDN'T HAVE A REMAINDER AND WAS DIVISIBLE BY K.

[@sharkoshen]

Very Clear and Helpful! Thanks a lot !

[@FluteVJ]

I've seen a lot of videos on this problem and this video is the best in explaining the solution. Thank you :)

[@isma5627]

Wow, that is very nice explanation. Thank you man!

[@rsKayiira]

Great video!!

[@djimgoudany]

Thanks great explanation

[@venkatsaireddy1412]

Such a good example for the divisible by k (1,21).

[@aquazod8366]

Thank you!

[@AndrewCLC]

This was very useful for understanding the reasoning. thank you. I went through a bunch of other videos and your reasoning at 3:30-4:30 is what made it most useful to me. The "philosophical rant" was fine too, it's reassuring for those of us who couldn't figure it out from a cold start.

[@AndrewCLC]

constructive criticism (and for anyone else coming to this that struggled) -- at 7:30 it gets a little confusing why you just added 3 to the total and didn't update the map. I reasoned this out: At -3, the remainder of 4 % 5 is 4. Map becomes {4=>4} Result is [-2,-3], [-2,-3,0], [-2,-3, 0, 5]. You add the current plus everything before. Result = 6. So if there was another X%5=4 down the line, it would be [x], [x,-2,-3], [x, -2, -3, 0] and [z, -2, -3, 0, 5],

[@subee128]

Thank you so much

[@aaditya_87]

good shit brh

[@katignaneshwar8647]

Very good explanation bro

[@khaleabhishek5023]

amazing video only video i would prefer specially for this problem

[@sarayarmohammadi3376]

Using defultdict(int), every remainder that is calculated will be 'present' in the remainders defaultdict, and it will have a default value of 0 if it hasn't been encountered before. So the if statement on line 11 will be true for all the keys. right? Maybe we can remove the if and just keep "count += remainders[running_sum % k]"?

[@estambuleno]

Nice explanation. Thank you. The if statement is redundant though

[@MinhNguyen-lz1pg]

the question is so dangerous that the police has to warn us

[@MrZiyak99]

space would be O(k) cause the map would have max k elements since you're taking the modulo