Sponsored
Sponsored
The idea is to use a running or cumulative sum and check the remainder when this sum is divided by k. If any two prefix sums have the same remainder, the subarray sum between these indices is divisible by k.
We maintain a hashmap to store each remainder and its index. As we iterate over the array, we update the running sum and check its remainder. If the remainder has been seen before and the subarray length is at least 2, we return true. If not, we continue. If we finish the loop without finding such a subarray, we return false.
Time Complexity: O(n), where n is the length of nums, since we iterate over the array only once.
Space Complexity: O(k), as we use a hashmap (or array) to store remainders which can be 0 through k-1 in the worst case.
1#include <unordered_map>
2#include <vector>
3#include <iostream>
4using namespace std;
5
6bool checkSubarraySum(vector<int>& nums, int k) {
7 unordered_map<int, int> remainderMap;
8 remainderMap[0] = -1;
9 int sum = 0;
10 for (int i = 0; i < nums.size(); ++i) {
11 sum += nums[i];
12 int mod = sum % k;
13 if (mod < 0) mod += k;
14 if (remainderMap.count(mod)) {
15 if (i - remainderMap[mod] > 1) return true;
16 } else {
17 remainderMap[mod] = i;
18 }
19 }
20 return false;
21}
22
23int main() {
24 vector<int> nums = {23, 2, 4, 6, 7};
25 int k = 6;
26 cout << (checkSubarraySum(nums, k) ? "true" : "false") << endl;
27 return 0;
28}This C++ implementation utilizes the STL unordered_map to serve as our hashmap for tracking remainders and their indices.
In each iteration, the code calculates the cumulative sum and its modulo with k, handling potential negative mods by adding k. If this remainder was previously recorded and the array's length between those indices is greater than 1, it returns true, indicating we've found our valid subarray.
This approach attempts every possible subarray of length at least 2, calculating the sum for each and checking if it is a multiple of k. Although not efficient, this serves as a basic solution for smaller inputs.
The process involves iterating over each possible starting point of a subarray, then for each starting point, iterating over each possible ending point to compute the sum, subsequently verifying its divisibility by k.
Time Complexity: O(n²) because of the nested loop structure iterating through potential subarray limits.
Space Complexity: O(1) as no extra space apart from a few variables is used.
class Program {
public static bool CheckSubarraySum(int[] nums, int k) {
for (int start = 0; start < nums.Length - 1; ++start) {
int sum = nums[start];
for (int end = start + 1; end < nums.Length; ++end) {
sum += nums[end];
if (sum % k == 0) return true;
}
}
return false;
}
static void Main() {
int[] nums = {23, 2, 4, 6, 7};
int k = 6;
Console.WriteLine(CheckSubarraySum(nums, k));
}
}In this C# example, every possible subarray is formed and verified for divisibility by k, predominantly depending on two nested loops to track start and end of subarrays applicable.
While effective in simple cases, it becomes inefficient with larger arrays due to repeated overlapping calculations.