forked from larissalages/code_problems
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path974.cpp
More file actions
30 lines (24 loc) · 806 Bytes
/
974.cpp
File metadata and controls
30 lines (24 loc) · 806 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
int subarraysDivByK(vector<int>& A, int K) {
int n= A.size(),j, cumSum= 0, res= 0, r;
//key is the remainder given by the prefix sum on division with k
//value is the count
unordered_map<int,int> m;
m[0]= 1;
for (j=0;j<n;j++){
cumSum+=A[j];
//r2-r can be 0, k,-k
//so r2 can be r, r+k, r-k;
r= cumSum%K;
res+= m[r];
res+= m[r+K];
res+= m[r-K];
m[r]++;
}
return res;
}
};
//===============================================================
//Time complexity of the above algorith: O(n), n is the length of the input array
//Space complexity: O(n), because of the hashmap