Subarray Sums Divisible by K Problem

Problem

Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

Examples

Example 1:

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

Example 2:

Input:
nums = [5], k = 9
Output:
 0

Solution

Method 1 - Using Prefix Sum Mod K and Map

This solution is similar to Continuous Subarray Sum Problem. As, we need to do subarray sums divisible by k, prefix sum with the modulus operator comes to mind.

When, we have 2 numbers x and y, such that

x % k = a
y % k = a

Here a is in range [0, k - 1] and x and y can be represented as:

x = a + m * k
y = a + n * k

So, difference between x and y is multiple of k:

x - y = (m - n) * k

Now, lets look at prefix sum and prefix sum mod k in example 1:

nums     =  [4, 5, 0,-2,-3, 1], k = 5
prefixSum = [4, 9, 9, 7, 4, 5]
   ..%k   = [4, 4, 4, 2, 4, 0]

Now, if you observe the prefixSumModK:

• For any subarray [i..j] whose sum is divisible by k, we can easily see that prefixSumModK[j] - prefixSumModK[i-1] = 0.

Thus if there are any repetitions in our prefixSumModK array, that represents a required subarray. So if we have the count of every possible value of prefixSumModK, we can determine if there are any subarray that end at the current index and the sum is divisible by k.

Handling negative reminders

Also, we may need to handle negative reminders, for eg. in Java. But reminder should be positive, and when, it goes below 0, then prefixSumModK then it doesn’t lie between [0, k - 1]. So, we can add k so that it likes between [0, k - 1].

Suppose k = 7 and you have a running sum of -2. The correct positive remainder when dividing -2 by 7 is not simply 2 (which is what you’d get if you multiplied by -1), but rather 5, since -2 + 7 = 5. So when you add 7 to -2, the result is within the range we expect for a modulus operation. So, we can just do:

reminder = num % k + k

Another way is:

if (prefixSumModK < 0) {
	prefixSumModK += k;
}

Video Explanation

Here is the video explanation:

Code

Java

class Solution {

	public int subarraysDivByK(int[] nums, int k) {
		Map<Integer, Integer> map = new HashMap<>();
		map.put(0, 1);
		int prefixSumModK = 0, count = 0;

		for (int num : nums) {
			prefixSumModK = (prefixSumModK + num % k + k) % k;
            
			int currCount = map.getOrDefault(prefixSumModK, 0);
			count += currCount;
			map.put(prefixSumModK, currCount + 1);
		}

		return count;
	}
}

Code with if condition

class Solution {

	public int subarraysDivByK(int[] nums, int k) {
		Map<Integer, Integer> map = new HashMap<>();
		map.put(0, 1);
		int prefixSumModK = 0, count = 0;

		for (int num : nums) {
			prefixSumModK += num;
			prefixSumModK %= k;

			if (prefixSumModK < 0) {
				prefixSumModK += k;
			}
			int currCount = map.getOrDefault(prefixSumModK, 0);
			count += currCount;
			map.put(prefixSumModK, currCount + 1);
		}

		return count;
	}
}

Complexity

• Time: O(n)
• Space: O(k)

Dry Run

We can see that nums = [4, 5, 0,-2,-3, 1], k = 5

Initially prefixSumModK = 0 and map = {0: 1}

Here is the detailed dry run:

1. Start with prefixSumModK = 0 and count = 0.

2. Process the first number (4):

    prefixSumModK = (0 + 4) % 5 = 4
    No adjustment needed since prefixSumModK is not negative.
    There are currently 0 subarrays ending here with a sum (mod 5) of 4.
    Increment the count in the map for the key 4.
   
    prefixSumCount = {0=1, 4=1}
    count += 0 (no subarrays end here which sum to a multiple of k)
   

3. Process the second number (5):

    prefixSumModK = (4 + 5) % 5 = 4
    No adjustment needed.
    There is 1 subarray ending here with sum (mod 5) of 4 ([4,5]).
    Increment the count in the map for the key 4.
   
    prefixSumCount = {0=1, 4=2}
    count += 1 (one subarray found so far that sums to a multiple of k)
    (subarrays = [ [5] ])
   

4. Process the third number (0):

    prefixSumModK = (4 + 0) % 5 = 4
    No adjustment needed.
    There are currently 2 subarrays ending here with sum (mod 5) of 4 (because we've seen prefixSumModK = 4 twice before; [4,5,0] and [0] - the last is empty to current index sum).
    Increment the count in the map for the key 4.
   
    prefixSumCount = {0=1, 4=3}
    count += 2 (total 3 subarrays found so far that sum to a multiple of k)
    (subarrays = [ [5], [5, 0], [0] ])
   

5. Process the fourth number (-2):

    prefixSumModK = (4 - 2) % 5 = 2
    No adjustment needed as "-2 % 5" is treated as "+3" in Java.
    There are currently 0 subarrays ending here with sum (mod 5) of 2.
    Increment the count in the map for the key 2.
   
    prefixSumCount = {0=1, 4=3, 2=1}
    count += 0 (still 3 subarrays found that sum to a multiple of k)
   

6. Process the fifth number (-3):

    prefixSumModK = (2 - 3) % 5 = 4
    No adjustment needed as "-3 % 5" is treated as "+2" in Java.
    There are currently 3 subarrays ending here with sum (mod 5) of 4 (because we've seen prefixSumModK = 4 three times before; [4,5,0,-2,-3], [0,-2,-3], and [-3] - the last is empty to current index sum).
    Increment the count in the map for the key 4.
   
    prefixSumCount = {0=1, 4=4, 2=1}
    count += 3 (total 6 subarrays found so far that sum to a multiple of k)
    (subarrays = [ [5], [5, 0], [0], [-2, -3], [0, -2, -3], [5, 0, -2, -3] ])
   

7. Process the sixth number (1):

    prefixSumModK = (4 + 1) % 5 = 0
    There is 1 subarray ending here with a sum (mod 5) of 0.
    Increment the count in the map for the key 0.
   
    prefixSumCount = {0=2, 4=4, 2=1}
    count += 1 (total 7 subarrays found that sum to a multiple of k)
    (subarrays = [ [5], [5, 0], [0], [-2, -3], [0, -2, -3], [5, 0, -2, -3], [4, 5, 0, -2, -3, 1] ])
   

By the end of the array, we have found 7 contiguous subarrays that have sums divisible by 5 (k). The map tells us how many times each sum modulo k occurs, and that helps us to count the subarrays efficiently.

The algorithm returns count = 7.