Hi megatron_64,

if the input numbers are in array “arr” and “K” is given in the question.

Let me define prefix_sum[i] = arr[0] + arr[1] + … arr[i]

if prefix_sum[i] % K == prefix_sum[j]%K for i < j

then

For example prefix_sum[i]%K = 3, prefix_sum[j]%K = 3 for i < j

what it means ??? Just think… that is in between i and j there is array sum which is

divisible by K right ? ===> sum of array for indices (i, j] is divisible by K.

Now generalize this. Take an of size K:===> that is reminder[K]

```
for i 0 to N-1:
remainder[prefix_sum[i]%K]++
```

what the above means is… for a particular “remainder value”, store the count of indices where you are getting that remainder.

Lets take an example:

For remainder 3 assume indices which gives prefix_sum[i]%K == 3 are 5, 8, 10, 20, 23.

5, 8, 10, 20, 23 ==> so how many Subsequences are possible ???

[6-8],

[6-10], [9-10],

[6-20], [9-20], [11-20],

[6-23], [9-23], [11-23], [21-23].

So you got the logic right???

ans = (n*(n-1))/2

But for remainder “0” if there are indices 5, 8, 10, 20, 23.

like this, then there is small change. Because

[0-5], [0-8], [0-10], [0-20], [0-23] are also added as a correct Subsequences.

thats y we initialize remainder[0] = 1, else 0’s

Thats it