Divisible subarrays

#1

i dont understand the whole concept of divisble subarrays
please explain it to me the whole thing competely.
thanks

#2

@mkidwai74 I dont think I can explain better in text than sir has explained in the video. I’d suggest you to rewatch the video at a slower pace if that helps. In case you still dont understand,
firstly, subarrays are contiguous. So if array is {1,2,3}, {1,3} will not be considered a subarray.
We have to find those subarrays whose sum is divisible by N. Here, N is the number of elements in the TOTAL array.
Finding sum of each subarray bu brute force will be an expensive operation, so we can make a cumulative sum array. This way, sum of subarray (i, j) can be given by csum[j] - csum[i] The exact formula has been explained in the video.

Now, we have to find a subarray sum which is divisible by N, ie (b-a) % N == 0
This can be broken down as b%N == a%n
So the question boils down to finding elements of csum with the same values.

How does pigeonhole principle come into play?
size of csum is n+1, and the range of elements of csum will be from 0->n-1 because we are taking mod with n. So,pigeonhole principle guarantees that there will be AT LEAST 2 elements, with the same value. We have to find all such pairs,which have the same values, and calculate the final answer based on that.

Please mark the doubt as resolved if I have cleared your confusion.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.