## DEV Community is a community of 718,675 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

sphoorthi

Posted on

# Leetcode: Continuous Subarray Sum

523. Continuous Subarray Sum

## Problem:

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7], k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7], k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Constraints:

The length of the array won't exceed 10,000.
You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

## Solution

The continuous sub array problems usually ask to find if there is a continuous sub array in array nums of a minimum length "l" which is multiple of a given target K

For any array nums with length n and the indices in order 0, i, j - where o < i < j < n [0, ...., i, ...., j, ... n-1]

• Consider sumI = sum of elements from 0th index to ith index. (nums+.....+nums[i]) and modI_K = remainder of sumI divided by K (i.e. modI_K = sumI % K)
• Consider sumJ = sum of elements from 0th index to jth index. (nums+.....+nums[j]) modJ_K = remainder of sumJ divided by K (i.e. modJ_K = sumJ % K)
• By remainder theorem,
Given any integer A, and a positive integer B, there exist unique integers Q and R such that
A = B * Q + R where 0 ≤ R < B

To put it in mathematical terms,
Running sum from first element to index i (sumI) when divided by K, the modI_K and sumI can be writtern as
sumI = K * x + modI_K
Running sum from first element to index j (sumJ) when divided by K, the modJ_K and sumJ can be writtern as
sumJ = K * x + modJ_K

If mods of sumI and sumJ are equal modI_K == modJ_K it means that the difference between sumI and sumJ results in a constant multiplied by K.
sumI - sumJ = constant * K
That means there must exist a subarray sum that is a multiple of k.

• So, to tackle these type of problems we need to save the remainders of running sum to help us identify that two running sums have a complimentary sum that is a multiple of K.

``````    public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> remainderMap = new HashMap<>();

remainderMap.put(0, -1);
int runningSum = 0;
int minLen = 2;

for(int i = 0; i < nums.length; i++) {
runningSum += nums[i];
if(k != 0) {
runningSum = runningSum % k;
}
if(remainderMap.containsKey(runningSum)) {
if(i - remainderMap.get(runningSum) >= minLen)
return true;
} else {
remainderMap.put(runningSum, i);
}
}
return false;
}
``````