Continuous Subarray Sum

Problem Statement

The task is to determine if an array, nums, contains at least one subarray (a contiguous segment of the array) that meets the following criteria:

• The length of the subarray is at least two.
• The sum of the elements in the subarray is a multiple of a given integer k.

A detailed explanation of the terms:

• A subarray refers to a sequence of elements from the array that are contiguous, meaning they appear in unbroken succession within the array.
• An integer being a multiple of k signifies that there exists some integer n such that multiplying k by n results in that integer. This includes zero, as zero is a multiple of every integer.

The function should return true if such a subarray exists, otherwise, it should return false.

Examples

Example 1

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.

Example 2

Input:

nums = [23,2,6,4,7], k = 6

Output:

true

Explanation:

[23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.

Example 3

Input:

nums = [23,2,6,4,7], k = 13

Output:

false

Constraints

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= sum(nums[i]) <= 231 - 1
• 1 <= k <= 231 - 1

Approach and Intuition

Based on the problem, to find a solution, we need to:

1. Check for every possible subarray of length at least two.
2. Calculate the sum of each of these subarrays.
3. Determine if this sum is divisible by k (i.e., sum % k == 0).

The task requires managing large arrays efficiently within the constraints provided, which calls for an approach that reduces repeated calculations:

• Prefix Sum: You can use a prefix sum array to quickly compute the sum of any subarray in constant time after an initial pre-processing step.
• Using Modulus for Efficiency: Instead of computing large sums directly, utilize the remainder (mod k) of these sums. Using properties of mod, if at any two different indices in the prefix sum array, the modulus results are equal, the elements between these indices sum up to a multiple of k.

Given the constraints:

• The maximum length for nums is 10^5, which calls for an efficient solution probably better than O(n^2).
• Value k will also be large, so directly handling big numbers needs optimized mod operations.

The examples given enlighten the approach:

• Example 1: [2, 4] inside [23, 2, 4, 6, 7] sums up to 6, which is a multiple of k=6. The quick sum check here is valid, and the presence of this subarray meets all the conditions.
• Example 2: The entire array [23, 2, 6, 4, 7] itself sums up to a multiple of k=6 (42 = 7*6).
• Example 3: No subarray with a sum that is a multiple of k=13 exists, thus returning false.

For each example, ensure the method used can handle the array and k efficiently, and remember, performance is key due to potentially large inputs.

Solutions

class Solution {
public:
    bool hasSubarrayWithSum(vector<int>& arr, int divisor) {
        int cumulativeSumModulo = 0;
        unordered_map<int, int> moduloIndexMap;
        moduloIndexMap[0] = -1;
    
        for (int idx = 0; idx < arr.size(); idx++) {
            cumulativeSumModulo = (cumulativeSumModulo + arr[idx]) % divisor;
    
            if (moduloIndexMap.find(cumulativeSumModulo) != moduloIndexMap.end()) {
                if (idx - moduloIndexMap[cumulativeSumModulo] > 1) {
                    return true;
                }
            } else {
                moduloIndexMap[cumulativeSumModulo] = idx;
            }
        }
    
        return false;
    }
};