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
        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[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
        Dictionary map = 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;
    }
}