Approach 1: Prefix Sums and Counting
As is typical with problems involving subarrays, we use prefix sums to add each subarray. Let
P[i+1] = A + A + ... + 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
K, or equivalently
P[j] are the same value modulo
Count all the
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 , , , , , .
Time Complexity: , where is the length of
Space Complexity: . (However, the solution can be modified to use space by storing only
Analysis written by: @awice.