Problem Statement

You are given an integer array nums and an integer k. Your task is to determine if there exists a contiguous subarray of size at least two whose sum is a multiple of k. In other words, check if there is a subarray where the sum of its elements is k times some integer (sum = n * k where n is any integer).

• Return true if such a subarray exists, otherwise 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 and its sum is
6, which is a multiple of 6.

Example 2:

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

Explanation: [23, 2, 6, 4, 7] has a subarray [2, 6, 4] with sum 12, which is a multiple of 6.

Example 3:

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

Different Approaches

1️⃣ Brute Force Approach

Code:

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        for (int i = 0; i < nums.size(); i++) {
            int sum = nums[i];
            for (int j = i + 1; j < nums.size(); j++) {
                sum += nums[j];
                if (k == 0) {
                    if (sum == 0) return true;
                } else if (sum % k == 0) {
                    return true;
                }
            }
        }
        return false;
    }
};

Complexity Analysis:

• Time Complexity: O(n^2)
  • Two nested loops over the array.
• Space Complexity: O(1)
  • Constant space is used.

2️⃣ Cumulative Sum with Remainder (Using Hash Map)

Property:

If two cumulative sums at different indices have the same remainder when divided by k, then the sum of the elements between those indices is a multiple of k.

Idea:

• The key observation here is that if two cumulative sums (prefix sums) have the same remainder when divided by k, then the subarray between these two sums has a sum that is a multiple of k.
• We can use the modulus (% k) to keep track of remainders, and a hash map to store the index where each remainder was first seen.
• If at any point we find the same remainder again and the subarray length is at least 2, then that subarray's sum is a multiple of k.

Steps:

1. Iterate through the array, maintaining a cumulative sum.
2. At each step, compute the remainder of the cumulative sum when divided by k (handle both positive and negative values of k).
3. Use a hash map to store the index where each remainder was first seen.
4. If the same remainder is encountered again and the subarray length is greater than 1, return true.
5. If no such subarray is found, return false.

Dry Run:

Initialization:

       +-----+-----+-----+-----+-----+
nums = | 23  |  2  |  4  |  6  |  7  |
       +-----+-----+-----+-----+-----+
          0     1     2     3     4

k = 6

remainderMap =  key  value
              +-----+-----+
              |  0  |  -1 |
              +-----+-----+

cumulativeSum = 0

First Iteration:

       +-----+-----+-----+-----+-----+
nums = | 23  |  2  |  4  |  6  |  7  |
       +-----+-----+-----+-----+-----+
          0     1     2     3     4
          ^
          |
          i
k = 6

remainderMap =  key  value
              +-----+-----+
              |  0  |  -1 |
              +-----+-----+

cumulativeSum = 0

    Add current element to cumulativeSum
    cumulativeSum = 0 + nums[i]
                  = 0 + 23
                  = 23
    Calculate remainder of cumulativeSum
    remainder = cumulativeSum % 6
              = 23 % 6
              = 5
    Check if remainder 5 exists in remainderMap as key. It doesnt.
    Add remainder 5 to remainderMap along with its index which is {5, 0}

Second Iteration:

       +-----+-----+-----+-----+-----+
nums = | 23  |  2  |  4  |  6  |  7  |
       +-----+-----+-----+-----+-----+
          0     1     2     3     4
                ^
                |
                i
k = 6

remainderMap =  key  value
              +-----+-----+
              |  0  |  -1 |
              +-----+-----+
              |  5  |  0  |
              +-----+-----+

cumulativeSum = 23

    Add current element to cumulativeSum
    cumulativeSum = 23 + nums[i]
                  = 23 + 2
                  = 25
    Calculate remainder of cumulativeSum
    remainder = cumulativeSum % 6
              = 25 % 6
              = 1
    Check if remainder 1 exists in remainderMap as key. It doesnt.
    Add remainder 1 to remainderMap along with its index which is {1, 1}

Third Iteration:

       +-----+-----+-----+-----+-----+
nums = | 23  |  2  |  4  |  6  |  7  |
       +-----+-----+-----+-----+-----+
          0     1     2     3     4
                      ^
                      |
                      i
k = 6

remainderMap =  key  value
              +-----+-----+
              |  0  |  -1 |
              +-----+-----+
              |  5  |  0  |
              +-----+-----+
              |  1  |  1  |
              +-----+-----+

cumulativeSum = 25

    Add current element to cumulativeSum
    cumulativeSum = 25 + nums[i]
                  = 25 + 4
                  = 29
    Calculate remainder of cumulativeSum
    remainder = cumulativeSum % 6
              = 29 % 6
              = 5
    Check if remainder 5 exists in remainderMap as key. It does (found at 
    index 0).
    Now check if the subarray length is at least 2.
        = i - remainderMap[5]
        = 2 - 0
        = 2 (valid subarray length)
        Therefore return true, since the subarray from index 1 to 2
        [2, 4] has a sum that is a multiple of k (sum is 6, which is divisible
        by 6.)

Code:

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        // Hash map to store remainder and its corresponding index
        unordered_map<int, int> remainderMap;
        remainderMap[0] = -1; // Initialize remainder 0 at index -1 for edge cases
        
        int cumSum = 0; // Cumulative sum
        
        for (int i = 0; i < nums.size(); i++) {
            cumSum += nums[i]; // Update cumulative sum
            
            // If k is not zero, compute remainder
            if (k != 0) {
                cumSum %= k;
            }
            
            // Check if the remainder has been seen before
            if (remainderMap.find(cumSum) != remainderMap.end()) {
                // If the same remainder was seen at a previous index and the subarray length is >= 2
                if (i - remainderMap[cumSum] > 1) {
                    return true; // Subarray sum is multiple of k
                }
            } else {
                // Store the index of this remainder
                remainderMap[cumSum] = i;
            }
        }
        
        return false; // No valid subarray found
    }
};

Explanation:

• Hash Map: Stores the remainder of the cumulative sum modulo k and its corresponding index.
• Remainder Handling: If two cumulative sums give the same remainder, the sum of the elements between them must be a multiple of k.
• Edge Case: We initialize the hash map with remainder 0 at index -1 to handle cases where a valid subarray starts from the beginning of the array.

Complexity Analysis:

• Time Complexity: O(n)
  • We make a single pass over the array.
• Space Complexity: O(min(n, k))
  • The hash map stores at most n or k remainders, whichever is smaller.