Subarray Sums Divisible by K

Problem:

Given an array "nums" of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by k.

Example, nums = [4,5,0,-2,-3,1], k = 5 ans should be 7

[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3] the sum of this subarrays are divisible by 5.

Approach:

This Problem is similar to Subarray Sum Equals K , the difference is here  we have to find number of subarray is divisible by K.

Approach will be same as before, in every position of given array we will check have we already met its remainder (pSum%k)  or not.

Similarly we will maintain A prefix sum and a Hashing Map.

Corner Case: Hense, there will be negative value, so its possible to have negative ramainder, so we have to make it positive by adding +k.

Simple Code:

Subarray Sums Divisible by K

Again, we count every occurences of remaider that we already met.

Now we will see how it works actually.

See, we calculating result help with prefix sum. Means that every time we need index 'j'(j < i) that is (pSum[i] - pSum[j])%k==0

Now from modular arithmatics, 

     (pSum[i] - pSum[j]) = k*X

=>pSum[j] = pSum[i] - k*X

=>pSum[j] % k = (pSum[i] - k*X)%k [taking mod both sides]

=>pSum[j] % k = (pSum[i] % k - k*X%k)%k [distributive]

=>pSum[j] % k = (pSum[i]%k)%k [k*X%k will be 0]

=>pSum[j] % k = pSum[i]%k

so, we need to find the occurences of pSum[j]%k.