Continuous Subarray Sum

January 14, 2024

Problem #

Given an array of non-negative integers nums and an integer k, find if the array has a continuous subarray of size at least two that sums up to a multiple of k.

Example:

1. Input: nums = [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.

Solution Approach #

The solution uses a hashmap to store the remainder of the cumulative sum modulo k and their indices. If the same remainder appears again, it indicates that the subarray sum between these indices is a multiple of k.

Algorithm Steps #

1. Initialize a hashmap with a key of 0 and value -1 (to handle cases where the subarray starts from the first element).
2. Iterate through the array, calculating the cumulative sum.
3. Calculate the remainder of this sum modulo k.
4. If the remainder is already in the hashmap, and the distance between the current index and the stored index is greater than 1, return True.
5. If the remainder is not in the hashmap, add it along with the current index.
6. If no such subarray is found, return False.

Code (Python) #

def checkSubarraySum(nums, k):
    cumulative_sum = 0
    remainder_map = {0: -1}

    for i, num in enumerate(nums):
        cumulative_sum += num
        if k != 0:
            cumulative_sum %= k

        if cumulative_sum in remainder_map:
            if i - remainder_map[cumulative_sum] > 1:
                return True
        else:
            remainder_map[cumulative_sum] = i

    return False

# Test the function
print(checkSubarraySum([23, 2, 4, 6, 7], 6))  # Output: True

Time Complexity #

O(n), where n is the length of the array. The array is traversed once.

Space Complexity #

O(k), for the hashmap storing the cumulative sum remainders.