Divisible subarrays

#1

code : https://ide.codingblocks.com/s/206504

2 test cases passed… 3 showing TLE

#2

@chaman9 hey bro,apne basic brute force use ki hai islie TLE arha hai ,use efficient approach ,I am explaining it below:
Let there be a subarray (i, j) whose sum is divisible by k
sum(i, j) = sum(0, j) - sum(0, i-1)
Sum for any subarray can be written as q*k + rem where q
is a quotient and rem is remainder
Thus,
sum(i, j) = (q1 * k + rem1) - (q2 * k + rem2)
sum(i, j) = (q1 - q2)k + rem1-rem2

We see, for sum(i, j) i.e. for sum of any subarray to be
divisible by k, the RHS should also be divisible by k.
(q1 - q2)k is obviously divisible by k, for (rem1-rem2) to
follow the same, rem1 = rem2 where
rem1 = Sum of subarray (0, j) % k
rem2 = Sum of subarray (0, i-1) % k
So if any sub-array sum from index i’th to j’th is divisible by k then we can saya[0]+…a[i-1] (mod k) = a[0]+…+a[j] (mod k)

So we need to find such a pair of indices (i, j) that they satisfy the above condition

Hope you get it.Try it.Happy codind :slight_smile:

#3

okay thanks a lot… i will try out

#4

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.