Number of subarrays having sum multiple of k

Given an integer array arr[] and an integer K (greater than 0), the task is to count the subarray whose elements sum up to a multiple of K, else print -1.  A number x is a multiple of K if there exists an integer y such that x = y*k. Remember 0 is also a multiple of K.

Examples:

Input: arr[] = {4,2,7,6}, K = 6
Output: 2
Explanation: 
There are 2 subarray whose sum of the elements is a multiple of k: {4,2} , {6}

Input: arr[] = {0,0,1,-7,3}, K = 6
Output: 6
Explanation: 
The 3 subarrays whose sum is a multiple of 6 are: {0}, {0}, {0,0}, {1,-7}, {0,1,-7}, {0,0,1,-7}

Input: {0,1,2,0}, K = 2
Output: 1
Explanation: 
The required subarray sum multiple of k : {0}, {0}, {2,0}, {2} 

Approach:
The question is quite similar to subarray sum divisible by k. Here is the algorithm:

1. Create a variable cursum, to store the sum till the current index and count to store the count of subarrays sum multiple of K. Initialize cursum and count as 0.
2. Create an unordered_map mp to store key value as remainder of the cursum%K and mapped value as the count of it. Initialize mp[0] = 1,for the case when al the elements sum upto a multiple of K.
3. Run a loop from index 0 to n(array size) and do the following steps inside it:
   1. Cursum+=arr[index]
   2. Create a variable rem = sum%k, this variable store remainder attained till the current index.
   3. Find in the map mp if there is a subarray with same remainder as rem, it means that there exist a subarray between them with sum multiple of K and update count, count+=mp[rem].
   4. update rem in the map mp.

4. Return the count.

Below is the C++ implementation of the above algorithm:

// C++ program to find the count of subarrays with
// sum multiple of k.
#include <bits/stdc++.h>
using namespace std;


// Function to find count of all sub-arrays divisible by K
// modified to handle negative numbers as well
int subarrayMultipleK(int arr[], int n, int K)
{
	//Create an unordered map to store the remainder
	unordered_map<int,int>mp;
	//When whole subarray is multiple of K
	mp[0] = 1;
	
	//Varaible to store sum till current index
	int cursum = 0;
    
    //Variable to store the count of subarray 
    //having sum multiple of K 
    int count = 0;
	//Traverse the array and find the subarray 
	//sum multiple of K 

	for(int i=0;i<n;i++)
	{
	    //Update cursum
	    cursum+=arr[i];
	    
	    int rem = cursum%K;
      
	    //handle negative remainders
	    if(rem < 0)
	    {
	        rem += K;
	    }
	    
	    //Find if there a subarray with remainder 
	    //as rem in map, if present then
	    //the subarray between it is a multiple
	    //of K, update the count 
	    if(mp.find(rem)!=mp.end())
	    {
	        count += mp[rem];
	    }
	    
	    //Increment rem in the map
	    mp[rem]++;
	}

    //Return the count 
	return count;
}

// Driver program to run the case
int main()
{
	int arr[] = { 4, 2, 7, 6};
	int K = 6;
	int n = sizeof(arr) / sizeof(arr[0]);
	cout <<"Count of subarray multiple of "<<K<<": "<<subarrayMultipleK(arr, n, K) << endl;
	int arr1[] = { 0, 0, 1, -7, 3};
	K  = 6;
	n = sizeof(arr1) / sizeof(arr1[0]);
	cout<<"Count of subarray multiple of "<<K<<": "<<subarrayMultipleK(arr1, n, K) << endl;
	int arr2[] = {0, 1, 2, 0};
	K = 2;
	n = sizeof(arr2) / sizeof(arr2[0]);
	cout<<"Count of subarray multiple of "<<K<<": "<<subarrayMultipleK(arr2,n,K)<< endl;
 	return 0;
}

Output:

Count of subarray multiple of 6: 2
Count of subarray multiple of 6: 6
Count of subarray multiple of 2: 4

Time Complexity: O(n)
Space Complexity: O(n)