# Solution For Subarray Sums Divisible By K

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.

## Step by Step Implementation For Subarray Sums Divisible By K

class Solution { public int subarraysDivByK(int[] A, int K) { // edge case: if A is null or empty, return 0 if (A == null || A.length == 0) { return 0; } // create a map to store the remainder of each sum mod K Mapmap = new HashMap<>(); // put (0, 1) into the map initially because there is 1 way to get sum = 0 map.put(0, 1); // keep track of the running sum int sum = 0; // keep track of the number of subarrays with sum divisible by K int count = 0; // iterate through the array for (int num : A) { // update the running sum sum += num; // get the remainder of the sum mod K int remainder = (sum % K + K) % K; // if the map contains the remainder, that means we've seen // this remainder before, which means there is a subarray // with sum divisible by K if (map.containsKey(remainder)) { count += map.get(remainder); } // put the remainder into the map with value = 1 map.put(remainder, map.getOrDefault(remainder, 0) + 1); } return count; } }

def subarraySum(nums, k): # initialize a hashmap to store the remainders hashmap = {} # initialize the sum to 0 sum = 0 # initialize the count to 0 count = 0 # loop through the array for i in range(len(nums)): # add the current element to the sum sum += nums[i] # get the remainder remainder = sum % k # if the remainder is 0, that means we have found a subarray sum divisible by k if remainder == 0: count += 1 # if the hashmap already contains the remainder, that means we have found a subarray sum divisible by k if remainder in hashmap: count += hashmap[remainder] # if the hashmap does not contain the remainder, add it to the hashmap if remainder not in hashmap: hashmap[remainder] = 1 # return the count return count

var subarraySumsDivisibleByK = function(nums, k) { // create a hashmap to store the remainder of each number when divided by k // the key will be the remainder and the value will be the number of times it occurs let map = {}; // initialize the map with a default value of 0 for all remainders for (let i = 0; i < k; i++) { map[i] = 0; } // initialize a running sum and count variable let sum = 0; let count = 0; // loop through the nums array for (let i = 0; i < nums.length; i++) { // add the current number to the running sum sum += nums[i]; // get the remainder of the sum when divided by k let remainder = sum % k; // if the remainder is 0, that means we found a subarray sum that is divisible by k // so we increment the count if (remainder === 0) { count++; } // if the map contains the remainder, that means we found two numbers with the same remainder // which means the difference between those two numbers is also divisible by k // so we increment the count by the number of times the remainder occurs in the map // and then update the map with the new count if (map[remainder]) { count += map[remainder]; map[remainder] = count; } else { // if the map does not contain the remainder, we simply add it to the map map[remainder] = count; } } // return the count return count; };

class Solution { public: int subarraysDivByK(vector& A, int K) { int count = 0; int sum = 0; unordered_map map; map[0]++; for(int i=0; i public class Solution { public int SubarraysDivByK(int[] A, int K) { // create a hashmap to store the remainder when divided by K // key is the remainder, value is the number of times we've seen that remainder Dictionarymap = new Dictionary (); // initialize the hashmap with a default value of 0 for all remainders for(int i = 0; i < K; i++) { map.Add(i, 0); } // keep track of the running sum int runningSum = 0; int count = 0; // for each element in the array for(int i = 0; i < A.Length; i++) { // add the element to the running sum runningSum += A[i]; // get the remainder when divided by K int remainder = runningSum % K; // if the remainder is negative, make it positive by adding K if(remainder < 0) { remainder += K; } // if we've seen this remainder before, // that means there is a subarray with a sum divisible by K // so we add the number of times we've seen that remainder to our count if(map.ContainsKey(remainder)) { count += map[remainder]; } // increment the number of times we've seen this remainder in our hashmap map[remainder]++; } // return the count return count; } }