Count Subarrays With Sum Divisible By K

Given an integer array arr[] and an integer k, find the total number of contiguous subarrays whose sum is divisible by k.

Examples:

Input: arr[] = [4, 5, 0, -2, -3, 1], k = 5
Output: 7
Explanation: There are 7 subarrays whose sum is divisible by 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3] and [-2, -3].

Input: arr[] = [2, 2, 2, 2, 2, 2], k = 2
Output: 21
Explanation: All subarray sums are divisible by 2.

Input: arr[] = [-1, -3, 2], k = 5
Output: 0
Explanation: There is no subarray whose sum is divisible by 5.

[Naive Approach] - Iterating over all subarrays - O(n²) time and O(1) space

The idea is to iterate over all possible subarrays while maintaining their sum. Whenever the sum is divisible by k, increment the count.

#include <iostream>
#include <vector>

using namespace std;

int subCount(vector<int> &arr, int k) {
	int n = arr.size(), res = 0;	
  
	// Iterating over starting indices of subarray
	for(int i = 0; i < n; i++) {
    	int sum = 0;
      
		// Iterating over ending indices of subarray
        for(int j = i; j < n; j++) {
        	sum = (sum + arr[j]) % k;
            if(sum == 0)
                res += 1;
        }
    }
	return res;
}

int main() {
	vector<int> arr = {4, 5, 0, -2, -3, 1};
    int k = 5;
    
    cout << subCount(arr, k);
}

#include <stdio.h>

int subCount(int arr[], int n, int k) {
    int res = 0;

    // Iterating over starting indices of subarray
    for (int i = 0; i < n; i++) {
        int sum = 0;

        // Iterating over ending indices of subarray
        for (int j = i; j < n; j++) {
            sum = (sum + arr[j]) % k;
            if (sum == 0)
                res += 1;
        }
    }
    return res;
}

int main() {
    int arr[] = {4, 5, 0, -2, -3, 1};
    int k = 5;
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("%d", subCount(arr, n, k));
    return 0;
}

class GfG {
    static int subCount(int[] arr, int k) {
        int n = arr.length, res = 0;

        // Iterating over starting indices of subarray
        for (int i = 0; i < n; i++) {
            int sum = 0;

            // Iterating over ending indices of subarray
            for (int j = i; j < n; j++) {
                sum = (sum + arr[j]) % k;
                if (sum == 0)
                    res += 1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {4, 5, 0, -2, -3, 1};
        int k = 5;

        System.out.println(subCount(arr, k));
    }
}

def subCount(arr, k):
    n = len(arr)
    res = 0
    
    # Iterating over starting indices of subarray
    for i in range(n):
        sum = 0
        
        # Iterating over ending indices of subarray
        for j in range(i, n):
            sum = (sum + arr[j]) % k
            if sum == 0:
                res += 1
                
    return res

if __name__ == "__main__":
	arr = [4, 5, 0, -2, -3, 1]
	k = 5

	print(subCount(arr, k))

using System;
using System.Collections.Generic;

class GfG {    
    static int subCount(int[] arr, int k) {
        int n = arr.Length, res = 0;

        // Iterating over starting indices of subarray
        for (int i = 0; i < n; i++) {
            int sum = 0;

            // Iterating over ending indices of subarray
            for (int j = i; j < n; j++) {
                sum = (sum + arr[j]) % k;
                if (sum == 0)
                    res += 1;
            }
        }
        return res;
    }

    static void Main() {
        int[] arr = { 4, 5, 0, -2, -3, 1 };
        int k = 5;

        Console.WriteLine(subCount(arr, k));
    }
}

function subCount(arr, k) {
    let n = arr.length, res = 0;

    // Iterating over starting indices of subarray
    for (let i = 0; i < n; i++) {
        let sum = 0;

        // Iterating over ending indices of subarray
        for (let j = i; j < n; j++) {
            sum = (sum + arr[j]) % k;
            if (sum === 0)
                res += 1;
        }
    }
    return res;
}

// Driver Code
let arr = [4, 5, 0, -2, -3, 1];
let k = 5;

console.log(subCount(arr, k));

7

[Expected Approach] - Using Prefix Sum modulo k

The idea is to use Prefix Sum Technique along with Hashing. On observing carefully, we can say that if a subarray arr[i...j] has sum divisible by k, then (prefix sum[i] % k) will be equal to the (prefix sum[j] % k). So, we can iterate over arr[] while maintaining a hash map or dictionary to count the number of (prefix sum mod k). For each index i, the number of subarrays ending at i and having sum divisible by k will be equal to the count of occurrences of (prefix sum[i] mod k) before i.

Note: Negative value of (prefix sum mod k) needs to be handled separately in languages like C++, Java, C# and JavaScript, whereas in Python (prefix sum mod k) is always a non-negative value as it takes the sign of the divisor, that is k.

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int subCount(vector<int> &arr, int k) {
	int n = arr.size(), res = 0;
	unordered_map<int, int> prefCnt;
	int sum = 0;

	for(int i = 0; i < n; i++) {
      
    	// prefix sum mod k (handling negative prefix sum)
    	sum = ((sum + arr[i]) % k + k) % k;
      
        // If sum == 0, then increment the result by 1
		// to count subarray arr[0...i]
        if(sum == 0)
        	res += 1;
      
        // Add count of all starting points for index i
		res += prefCnt[sum];
      
        prefCnt[sum] += 1;
    }
	return res;
}

int main() {
	vector<int> arr = {4, 5, 0, -2, -3, 1};
    int k = 5;
    
    cout << subCount(arr, k);
}

import java.util.HashMap;
import java.util.Map;

class GfG {
    static int subCount(int[] arr, int k) {
        int n = arr.length, res = 0;
        Map<Integer, Integer> prefCnt = new HashMap<>();
        int sum = 0;

        for (int i = 0; i < n; i++) {

            // prefix sum mod k (handling negative prefix sum)
            sum = ((sum + arr[i]) % k + k) % k;

            // If sum == 0, then increment the result by 1
            // to count subarray arr[0...i]
            if (sum == 0)
                res += 1;

            // Add count of all starting points for index i
            res += prefCnt.getOrDefault(sum, 0);

            prefCnt.put(sum, prefCnt.getOrDefault(sum, 0) + 1);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {4, 5, 0, -2, -3, 1};
        int k = 5;

        System.out.println(subCount(arr, k));
    }
}

from collections import defaultdict

def subCount(arr, k):
    n = len(arr)
    res = 0
    prefCnt = defaultdict(int)
    sum = 0
    
    for i in range(n):
        sum = (sum + arr[i]) % k

        # If sum == 0, then increment the result by 1
        # to count subarray arr[0...i]
        if sum == 0:
            res += 1

        # Add count of all starting points for index i
        res += prefCnt[sum]

        prefCnt[sum] += 1

    return res

if __name__ == "__main__":
	arr = [4, 5, 0, -2, -3, 1]
	k = 5

	print(subCount(arr, k))

using System;
using System.Collections.Generic;

class GfG {
    static int subCount(int[] arr, int k) {
        int n = arr.Length, res = 0;
        Dictionary<int, int> prefCnt = new Dictionary<int, int>();
        int sum = 0;

        for (int i = 0; i < n; i++) {
          
            // prefix sum mod k (handling negative prefix sum)
            sum = ((sum + arr[i]) % k + k) % k;

            // If sum == 0, then increment the result by 1
            // to count subarray arr[0...i]
            if (sum == 0)
                res += 1;

            // Add count of all starting points for index i
            if (prefCnt.ContainsKey(sum))
                res += prefCnt[sum];

            if (prefCnt.ContainsKey(sum))
                prefCnt[sum] += 1;
            else
                prefCnt[sum] = 1;
        }
        return res;
    }

    static void Main() {
		int[] arr = { 4, 5, 0, -2, -3, 1 };
        int k = 5;

        Console.WriteLine(subCount(arr, k));
    }
}

function subCount(arr, k) {
    let n = arr.length, res = 0;
    let prefCnt = new Map();
    let sum = 0;

    for (let i = 0; i < n; i++) {

        // prefix sum mod k (handling negative prefix sum)
        sum = ((sum + arr[i]) % k + k) % k;

        // If sum == 0, then increment the result by 1
        // to count subarray arr[0...i]
        if (sum === 0)
            res += 1;

        // Add count of all starting points for index i
        res += (prefCnt.get(sum) || 0);

        prefCnt.set(sum, (prefCnt.get(sum) || 0) + 1);
    }

    return res;
}

// Driver Code
let arr = [4, 5, 0, -2, -3, 1];
let k = 5;

console.log(subCount(arr, k));

7

Time Complexity: O(n), as we are iterating over the array only once.
Auxiliary Space: O(min(n, k)), as at most k keys can be present in the hash map or dictionary.