Pattern 2: Subarray Sum Divisible by K ( Intuition + Mapping )

Subarray Sums Divisible by K:(https://leetcode.com/problems/subarray-sums-divisible-by-k/)

Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k. A subarray is a contiguous part of an array.

Example 1:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Intuition: Few points we need to check note here like —

1. It should be a subarray sum, not a subsequence, which means we can’t skip the element in between.
2. To check any sum is divisible by K, we can mod the operator ( all know that lol).

We know to calculate any subarray sum we can Prefix sum, how is that? let's see an example

nums=[ 1, 2, 3, 4, 5] Prefix sum= [1, 3, 6, 10, 15 ], If I want a sum from an index 2nd to 4th, let's say (l and r) range, I can use prefix array like = Prefix[r] — prefix[l–1]= 15–3 = 12

the prefix[i] means total sum till ith index from starting. Now we get some sense that we can use the prefix sum here, but it is not clear how it helps.

Bruteforce: One thing we can use that generate all the subarrays and take out some using a prefix array and check its divisible by K or not ( if yes count it ). But the time Complexity is O(n²) to generate all the subarray and use pre-computed prefix array in O(1) to get a sum. We can solve this in O(n) time also.

Optimal Solution:

Given nums = [4,5,0,-2,-3,1] and K = 5

Prefix sum till any index I (let's suppose 1st here is 9 = [4+5] ), We take modulo K that will be (9 % 5) = 4, What this means here? It tells you that there is a surplus of 4 in the sum ( If it is 0, that means it's perfectly divisible by K) but right now there are more than 4 in the sum.

Let's see the simple example nums = [4,5,0,-2,-3,1] and prefix_sum till the last index is 5 and it's divisible by K, which means the total sum of the array is divisible by K, so we count 1 for the complete array [4,5,0,-2,-3,1].

1. (31% 5) =1 ( Surplus of 1 ) 2. ( 17% 5) = 2 (Surplus of 2)

Taking advantage of this fact let's check another sum where from starting who give us 4.

nums = [4,5,0,-2,-3,1] and K = 5

{ [4], [4 + 5 ], [4+ 5 + 0], [4 + 5 + 0+ (-2) + (-3 )] }, There are four sub-array whose sum from starting gives 4 as surplus ( remember sum is from starting and taking modulo in last of subarray ).

No, we can say in this subarray [4], [4 + 5 ], [4+ 5 + 0], [4 + 5 + 0+ (-2) + (-3 )] there is the subarray in between that is divisible by K, wait but How? Because even after adding an element the surplus is still the same. We can conclude that there must be a subarray sum that gives us ZERO, which is why our surplus didn’t increase or decrease.

That is now!! we have to count that subarray that contributes nothing ( zero, nill ). We can say for every module like this, isn’t it?

Let's see how to do this :

nums = [4,5,0,-2,-3,1] and K = 5

Prefix sum = [ 4 , 9 , 9 , 7, 4, 5]
After taking  modulo by K = [  4 , 4 , 4,  2, 4 , 0 ]

Take a array sixe of K ( as max is K-1)and count occurence of element 
after taking modulo 

4 -> 4 times
0 -> 1 times
2->  1 times

How to count subarray out of it?

1. There the modulo occurrence is 1 or 0 times ( we neglect it, as its never divisible by K) ( Edges case: for key 0 because we have to count it, as it means it is perfectly divisible by K)
2. If it's more than 1: like 4 -> 4time, how many subarrays can we count like= (n * (n-1 ) /2 ) because we have to choose 2 ways from in between 4 subarrays, so there are nc2 ways ( 4c2 here) to do this. (4* 3)/2 = 6. It's a little tricky but thinks about this. ( In this problem we need only count, so don't care much which all subarray is)

Eg. 4 -> 4 times = 6 subarray = {[5], [5, 0], [5, 0, -2, -3], 
[0], [0, -2, -3], [-2, -3]}

How? 

1. Let's pick up with [4]
[4] , [4+ 5] => we can take [5] 
[4] , [4+5+0 ]=> we can count [5+0]
[4] , [4 + 5 + 0+ (-2) + (-3 )]=> we can count [5 + 0+ (-2) + (-3 )]

2. with [4+5] 
[4+5] , [4+5+0]= we can count [0]
[4+5], [4 + 5 + 0+ (-2) + (-3 )]= we can count [ 0+ (-2) + (-3 )]
and so on…..

Total would be 6 subarray

Total count = 7 subarray that is divisible by K

4 -> 4 times = 6 subarray = {[5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]}
0 -> 1 time = 1 subarray ( edge case ) [4,5,0,-2,-3,1]
2-> 1 time = 0 subarray

That is !!! Here is the code for the same:

int subarraysDivByK(vector<int>& nums, int k) {

        vector<int>arr(k,0);
        int sum=0;
     
        for(int i=0;i<nums.size();i++){
            sum+=nums[i];
            sum=sum%k;
            sum=(sum+k)%k; //handling negative modulo
            arr[sum]++;

        }
        
        int count=arr[0]; //edge case
        
      //nc2 ways to count
        for(int i=0;i<arr.size();i++)
            count+=((arr[i]*(arr[i]-1))/2);

        return count;
        
    }

Similar Problem Mapping:

1. Minimum subarray sum divisible by K: This is the same problem but we need to calculate the size of the min subarray, what we can do is store the index of the array of the same modulo.

nums = [4,5,0,-2,-3,1] and K = 5

Prefix sum = [ 4 , 9 , 9 , 7, 4, 5]
After taking  modulo by K = [  4 , 4 , 4,  2, 4 , 0 ]

Take a hashmap (key and value) and store the index of element after taking modulo 

4 -> { 0 , 1 , 2, 4} 
0 -> { 5 }
2->  {3} 

Now we can simple traverse to values of every key and calculate the minimum gap 
between them as that is divible by K.

Think on this !!!!
{ 0, 1 , 2 , 4} min gap is 1

means subrray with [5], [0]

Code i'm leaving on you!!

Thank you !!

My Pattern Series :

1. https://medium.com/@akash-kumar916/pattern-1-jump-game-leetcode-intuition-mapping-problems-f1821298ce4f