# Subarray Sum Divisible By K Problem

## Description

LeetCode Problem 974. Given an array of integers **nums** and an integer **k**, return the total number of continuous subarrays whose sum is divisible by **k**.

Example:

1
2
3
4

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]

## Solution

This problem is similar to the `subarray sum equals k problem`

.

#### Brute Force Approach

A simple solution is to use the `brute force`

approach. We can consider all possible subarrays and check whether the sum of each subarrays is divisible by *k*.

We can use a left pointer *l* and a right pointer *r* to enumerate all possible subarrays. We loop through each integer in the array *nums* with *l*. For each *l*, we iterate with *r* from *l*+1 to the end of the array. In the meantime, we use a *sum* variable to record the accumulative sum from *l* to *r*. If *sum* is divisible by *k*, we can increase the total count; otherwise, we can keep on searching.

The time complexity of this approach is O(n^{2}),
and the space complexity is O(1).

#### Hash Table Approach

The time complexity can be further reduced if we use a `hash table`

to store intermediate results.

We loop through the array and use an *accu_sum* variable to store the accumulative sum. During the iteration, we calculate the modulo (*accu_sum* % *k*). We then store the modulo to a hash table as a key and the number of occurrence of this modulo as the value.

During the iteration, if we have already found an *accu_sum* that has the same modulo with *k* as the current *accu_sum*, then the subarray between these two *accu_sum* has a sum divisible by *k*.

We can check how many same modulo has occurred before, that will be the number of subarrays whose sums are divisible by *k*. Thus, we can add the value of this modulo in the hash table to the total count.

Here is a complete walk through of the `hash table`

approach. The array *nums* is {4,5,0,-2,-3,1}, and *k* is 5.

1
2
3
4
5
6
7
8
9
10
11
12

| nums | accu_sum | modulo | ht
| 4 | 5 | 0 | -2 | -3 | 1 | - | - | (0,1) <-- count = 0
i | 4 | 4 | (0,1) (4,1) <-- No such subarray found
i | 9 | 4 | (0,1) (4,2) <-- The sum of subarray [1..1] is divisible by k
count = count+ht[modulo]-1 = 0+1 = 1
i | 9 | 4 | (0,1) (4,3) <-- The sum of subarray [1..2], [2..2] is divisible by k
count = count+ht[modulo]-1 = 1+2 = 3
i | 7 | 2 | (0,1) (4,3) (2,1) <-- No such subarray found
i | 4 | 4 | (0,1) (4,4) (2,1) <-- The sum of subarray [1..4] [2..4] [3..4] is divisible by k
count = count+ht[modulo]-1 = 3+3 = 6
i | 5 | 0 | (0,2) (4,4) (2,1) <-- The sum of subarray [0..5] is divisible by k
count = count+ht[modulo]-1 = 6+1 = 7

The time complexity can be reduced to O(n), and the space complexity is O(k).

## Sample C++ Code

This is a C++ implementation of the hash table approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
int subarraysDivByK(vector<int>& A, int K) {
int len = A.size();
unordered_map<int, int> ht;
int accu_sum = 0;
int count = 0;
int modulo;
ht[0] = 1;
for (int i = 0; i < len; i ++) {
accu_sum += A[i];
modulo = accu_sum % K;
if (modulo < 0)
modulo += K;
if (ht.find(modulo) == ht.end()) {
ht[modulo] = 0;
}
count += ht[modulo];
ht[modulo] ++;
}
return count;
}
int main() {
vector<int> nums={4,5,0,-2,-3,1};
int k = 5;
cout << subarraysDivByK(nums, k) << endl;
}