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
trueif such a subarray exists, otherwise returnfalse.
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: falseDifferent 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 ofk. - 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:
- Iterate through the array, maintaining a cumulative sum.
- At each step, compute the remainder of the cumulative sum when divided by
k(handle both positive and negative values ofk). - Use a hash map to store the index where each remainder was first seen.
- If the same remainder is encountered again and the subarray length is greater than 1, return
true. - 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 = 0First 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
kand 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
0at index-1to 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
norkremainders, whichever is smaller.
- The hash map stores at most