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[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,
  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;
    }

Thank you for reading :)

Comments

[Sesha Sai Srivatsav Kuchibhotla]

Thanks for great explanation. Could you help me understand remainderMap.put(0, -1); ?

[Sumit Sharma]

When runningSum was not started, means before 0th index of the array, we have Sum=0 and its index is -1.
We are storing it in case at some place we have remainder 0 (may be at first place or after some place with length more than 2) then to get the length of that and consider that sub-array we need this values stored before we start.
Hope you understand