Continuous Subarray Sum Problem

Problem

Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.

An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

Examples

Example 1:

Input:
nums = [23,2,4,6,7], k = 6
Output:
 true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

Example 2:

Input:
nums = [23,2,6,4,7], k = 6
Output:
 true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.

Example 3:

Input:
nums = [23,2,6,4,7], k = 13
Output:
 false

Solution

Method 1 - Using Prefix Sum Mod K and Map

Lets try to look at modulus operator. When we try x % k: $$ x \% k = a \tag 1 $$ then 0 <= a < k.

Now, suppose there is there another integer y and we do y % k and that is also equal to a. $$ y \% k = a \tag 2 $$ Then 0 <= a < k.

That means we have x = a + k*m and y = a + k * n.

Suppose, x = 2 and y = 100, and k = 7, then a = 2. Then x % k = 2 % 7 = 2, and y % k = 100 % 7 = 2.

Now, a in equation 1 can lie between 0 and k - 1. For eg. k = 7, then 2 % 7 = 2, 3 % 7 = 3, and so on.

Now, we have an array of numbers: $$ nums = [x_1, x_2, … x_n] $$

Then, lets look at different modulus operation results:

$$ x_1 \% k = a \tag 3 $$ $$ x_2 \% k = b \tag 4 $$ $$ (x_1 + x_2) \% k = c \tag 5 $$

In above a, b, c are all reminders. Then, we have distributive property of modulus:

(x1 + x2) % k = (x1 % k + x2 % k) % k

This implies that:

c = (a + b) % k

So, this implies:

It doesn’t matter if you’re adding the numbers themselves then performing modulus operation or adding the numbers to remainders from previous sums if what you care about is the remainder operation again.

Now, lets focus on reminders a, b and c again.

If a, b and c are all different, that means all a + b < k. For eg. k = 7, a = 1, b = 2, c = 3
But, if c is equal to a or b, that means it would have summed a multiple of k in between. For eg. k = 7, a = 2, b = 0, c = 2

Now, lets apply this to whole array. So, now we know If we use prefix sum alone, this solution may not help. But if we use mod operator on prefix sum, we can see above pattern. Take for eg.

nums = [23, 2, 1, 6, 7], k = 9

Now, lets try to sum them up: i = 0, x1 = 23, 23 % k = 5…lets call it a. i = 1, x2 = 2. One way is (23 + 2) % k = 7. But, if we apply the distributive property from above, then we can also do (a + 2) %k = (5 + 2) % k = 7 Similarly, we fill the whole array.

nums =             [23, 2, 1, 6, 7], k = 9
prefix sum mod k = [5,  7, 8, 5, 3]
					↑         ↑

We can see that at index 0 and 3, prefix sum mod k match. That means difference divided by k is actually matching. That is one of the continuous sums, hence we return true.

Algorithm

We create hashmap of prefixSumModK and array index.
Case 1 - If we see repeat of prefixSumModK , we should return try if difference in index is more than equal to 2.
Case 2 - 0 is also considered multiple of k. So, if we have sum equal to 0 at any point, we should have an answer. We can do so by adding 0, -1 in map initially.

Here is the video explanation:

Code

Java

class Solution {

	public boolean checkSubarraySum(int[] nums, int k) {
		Map<Integer, Integer> map = new HashMap<>() {
			{
				put(0, -1);
			}
		};
		int prefixSumModK = 0;

		for (int i = 0; i < nums.length; i++) {
			prefixSumModK += nums[i];
			prefixSumModK %= k;

			if (!map.containsKey(prefixSumModK)) {
				map.put(prefixSumModK, i);
				// prefixSumModK is in map but we should check array size
			} else if (i - map.get(prefixSumModK) > 1) {
				return true;
			}
		}

		return false;
	}
}

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(k)

Problem#

Examples#

Solution#

Method 1 - Using Prefix Sum Mod K and Map#

Algorithm#

Code#

Java#

Complexity#