# 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, 0], [5, 0, -2, -3], , [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 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%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_ 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
Map map = 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++;
for(int i=0; ipublic 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
Dictionary map = new Dictionary();

// initialize the hashmap with a default value of 0 for all remainders
for(int i = 0; i < K; i++) {
}

// 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;
}
}```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]