Leetcode: Continuous Subarray Sum
Tags: java, challenge
Published: 2020-06-09 04:56:40

[523. Continuous Subarray Sum](https://leetcode.com/problems/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[0]+.....+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[0]+.....+nums[j])
modJ_K = remainder of sumJ divided by K (i.e. modJ_K = sumJ % K)
- By [remainder theorem](https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-quotient-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.

```java
    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;
    }
```

Thank you for reading :)