In this problem how will you say that (b-a)%7 = b%7 - a%7

b,a are 2 values in prefix sum

(b-a)%7 = (b%7 - a%7)%7 right ?

I believe so. It *might* not be true in C++/Java because their % operator is a remainder operator rather than a true modulus operator, but I’m not sure.

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