Subarray Sums Divisible By K - Leetcode Solution

Problem Statement:

Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.

Example 1:

Input: A = [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]

Note:

• 1 <= A.length <= 30000
• -10000 <= A[i] <= 10000
• 2 <= K <= 10000

Solution:

In this problem, we need to find the number of subarrays whose sum is divisible by K. Let's say that we have an array A of size N and a prefix sum array prefix_sum of size (N+1). The prefix_sum array will store the cumulative sum of A upto index i. So prefix_sum[i] will store the sum of A[0:i]. Hence, prefix_sum[0] is 0 and prefix_sum[i+1] = prefix_sum[i] + A[i]. Now, we can find the sum of any subarray A[l:r] by using prefix_sum[r+1] - prefix_sum[l].

We want to find subarrays whose sum is divisible by K. Let's say, we have two subarrays A[l1:r1] and A[l2:r2] with sum S1 and S2 respectively such that S1 % K = S2 % K. This means (S1-S2) % K = 0.

Therefore, if prefix_sum[i] % K = x and prefix_sum[j] % K = x, then the sum of subarray A[i:j] is divisible by K.

We can use this property while iterating through the array A to find all subarrays whose sum is divisible by K. For each index i in A, we calculate its prefix sum prefix_sum[i+1] and take its modulo with K to get the remainder. We maintain a dictionary called count which stores the frequency of each remainder. Initially, we add 1 to the count of remainder 0 because prefix_sum[0]%K = 0.

Now, for each index i, we check whether there exists an index j such that prefix_sum[j]%K = prefix_sum[i+1]%K. If yes, then we add the count of remainder prefix_sum[j]%K to the answer because all subarrays between j and i+1 will have a sum divisible by K. Then, we increment the count of remainder prefix_sum[i+1]%K by 1.

We repeat this for all indices i in A and finally return the answer.

Code:

def subarraysDivByK(A, K): count = {0:1} #count of remainder 0 is initially 1 as prefix_sum[0]_ mod K = 0 prefix_sum = 0 #cumulative sum of A ans = 0 #number of subarrays with sum divisible by K

for i in range(len(A)):
    prefix_sum += A[i] #calculating prefix sum upto i
    remainder = prefix_sum % K #taking modulo with K
    if remainder in count:
        ans += count[remainder] #adding count of subarrays with same remainder
    count[remainder] = count.get(remainder,0) + 1 #incrementing count of current remainder
    
return ans

Complexity Analysis:

Time Complexity: O(N). We traverse the given array once and each array element is accessed once.

Space Complexity: O(K). The size of dictionary count is at most K because the remainder can take values from 0 to K-1.

1