Solution
Approach 1: Prefix Sums and Counting
Intuition
As is typical with problems involving subarrays, we use prefix sums to add each subarray. Let P[i+1] = A[0] + A[1] + ... + A[i]
. Then, each subarray can be written as P[j]  P[i]
(for j > i
). Thus, we have P[j]  P[i]
equal to 0
modulo K
, or equivalently P[i]
and P[j]
are the same value modulo K
.
Algorithm
Count all the P[i]
's modulo K
. Let's say there are values . Then, there are possible subarrays.
For example, take A = [4,5,0,2,3,1]
and K = 5
. Then P = [0,4,9,9,7,4,5]
, and :
 With (at , ), it indicates subarray with sum divisible by , namely .
 With (at , , , ), it indicates subarrays with sum divisible by , namely , , , , , .
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: . (However, the solution can be modified to use space by storing only
count
.)
Analysis written by: @awice.