Solution For Continuous Subarray Sum

Problem Statement

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.

A continuous subarray is a subarray that appears in consecutive positions in the array.

Example:

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.

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

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

Solution

First of all, we need to understand the problem statement. We need to find a continuous subarray of size at least two whose elements sum up to a multiple of k.

To solve this problem, we can use a prefix sum approach. We can create an array of prefix sums for nums, where prefix[i] = nums[0] + nums[1] + … + nums[i-1]. Then, we can iterate through prefix and check if there are any two indices i and j (i < j) such that (prefix[j] – prefix[i]) % K == 0. If we find such indices, we return true. Otherwise, we return false.

Here are the steps to implement the solution:

• Create an array prefix of size n+1, where n is the length of nums.
• Initialize prefix[0] to 0.
• Iterate through nums, and at each iteration i, set prefix[i+1] = prefix[i] + nums[i].
• Initialize a set seen to store the modulus of prefix[i] with k.
• Iterate through prefix, and at each iteration i, check if (prefix[i] % k) is in seen. If it is, return true. Otherwise, add (prefix[i] % k) to seen.
• Return false if you have not found a proper subarray.

Let’s look at the code to implement this solution:

Python Code

def checkSubarraySum(nums, k):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i+1] = prefix[i] + nums[i] seen = set()
for i in range(1, n+1):
mod = prefix[i] % k
if mod in seen:
return True
seen.add(prefix[i-1] % k)
return False

Time Complexity

The time complexity of this solution is O(n), where n is the length of nums. We are iterating through nums twice, which takes O(n) time. We are also using a set to store seen values, which takes O(1) time on average for each check or add operation.

Space Complexity

The space complexity of the solution is O(n) as we are using prefix and seen arrays of size n+1 and a set of size at most K (where K is the input parameter).

Step by Step Implementation For Continuous Subarray Sum

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        //edge case
        if(nums == null || nums.length == 0) return false;
        
        //use hashmap to store the running sum mod k
        Map map = new HashMap<>();
        //if the running sum mod k equals to 0, we find a subarray
        map.put(0, -1);
        int runningSum = 0;
        for(int i = 0; i < nums.length; i++){
            runningSum += nums[i];
            if(k != 0) runningSum %= k;
            Integer prev = map.get(runningSum);
            if(prev != null){
                //check if there is at least one number between the current number and the previous number
                if(i - prev > 1) return true;
            }
            else map.put(runningSum, i);
        }
        return false;
    }
}

def continuousSubarraySum(self, A):
        # write your code here
        if not A:
            return 
        res = A[0]
        cur = A[0]
        for i in xrange(1, len(A)):
            cur = cur + A[i] if cur > 0 else A[i]
            res = max(res, cur)
        return res

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var checkSubarraySum = function(nums, k) {
    // edge case where k is 0
    if (k === 0) {
        for (let i = 0; i < nums.length - 1; i++) {
            if (nums[i] === 0 && nums[i+1] === 0) {
                return true;
            }
        }
        return false;
    }
    
    // map to store the running sum mod k
    let map = { 0: -1 };
    let runningSum = 0;
    
    for (let i = 0; i < nums.length; i++) {
        runningSum += nums[i];
        let mod = runningSum % k;
        
        // if the modulus has been seen before, we know there is a subarray with a sum divisible by k
        if (map[mod] !== undefined) {
            // the subarray must have at least 2 elements
            if (i - map[mod] > 1) {
                return true;
            }
        } else {
            // otherwise, add the modulus to the map
            map[mod] = i;
        }
    }
    
    return false;
};

class Solution {
public:
    bool checkSubarraySum(vector& nums, int k) {
        int n = nums.size(); 
  
        // Hash map to store cummulative 
        // sum mod k and its position 
        unordered_map map; 
        int cum_sum = 0; 
  
        for (int i = 0; i < n; i++) { 
  
            // Calculate cummulative sum 
            cum_sum += nums[i]; 
  
            // Cum sum can be k also so 
            // handle that 
            if (cum_sum == k) 
                return true; 
  
            // If cum_sum > k then do mod 
            // with k and check if this mod 
            // exists in hash map or not 
            if (cum_sum > k) 
                cum_sum = cum_sum % k; 
  
            // If this sum is seen before, 
            // then subarray exists 
            if (map.find(cum_sum) != map.end()) 
                return true; 
            else
                map[cum_sum] = i; 
        } 
        return false; 
    } 
};

public class Solution {
    public bool CheckSubarraySum(int[] nums, int k) {
        //check for edge case where k is 0 and there are two 0s in a row
        for(int i = 0; i < nums.Length - 1; i++) {
            if(nums[i] == 0 && nums[i + 1] == 0) {
                return true;
            }
        }
        
        //if k is 0 or 1, then we can just check if there are two consecutive numbers that are equal
        if(k == 0 || k == 1) {
            for(int i = 0; i < nums.Length - 1; i++) {
                if(nums[i] == nums[i + 1]) {
                    return true;
                }
            }
        }
        
        //otherwise, we can use a hashtable to keep track of the running sum mod k
        //if we ever see the same running sum mod k twice, then we know there is a subarray with sum divisible by k
        var map = new Dictionary();
        map.Add(0, -1); //add base case of sum = 0 at index = -1
        int sum = 0;
        for(int i = 0; i < nums.Length; i++) {
            sum += nums[i];
            //if k is not 0, we can take the mod, otherwise we just need to check if the sum is divisible by k
            int key = k == 0 ? sum : sum % k;
            if(map.ContainsKey(key)) {
                if(i - map[key] > 1) { //make sure there are at least 2 numbers in the subarray
                    return true;
                }
            }
            else {
                map.Add(key, i);
            }
        }
        return false;
    }
}