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.