LC 974

Goal:
Given an array of integers, count number of subarrays that have sums that are divisible by K, where 2 ≤ K ≤ 10000. The subarray size should be at least 1.

Intuition:
The naive way is to try all the subarrays in nested loops. That will take O(n³).
That is very inefficient. We can use additional data structure to reduce the time complexity. Mathematically, we have the following relation:

(a + n*k) % k == a % k

According to above relation, we can see that if two number have same remainder, their difference must be divisible by k. Thus, we can maintain a running total and use a hashtable to store the running total mod K (remainder) to frequency mapping so far, similar to two sum technique, if the remainder is already in the hashtable, we can add the count of that remainder to the total count of qualified subarrays.

Time: O(size of input), Space: O(K)