blob: 3661c96db8e601369a79d72c44d1423305b9bee2 (
plain)
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
31
32
|
// 974. Subarray Sums Divisible by K
#include "leetcode.h"
#include <vector>
/*
* given: integer array 'nums' and integer 'k'
* return: number of non-empty subarrays that
* have a sum divisible by 'k'.
* a subarray is a contiguous part of an array
*/
class Solution {
public:
int subarraysDivByK(vector<int> &nums, int k) {
vector<int> count(k);
count[0] = 1;
int prefix = 0, ans = 0;
for (int i : nums) {
prefix = (prefix + i % k + k) % k;
ans += count[prefix]++;
}
return ans;
}
};
int main() {
Solution obj;
vector<int> nums1 = {4, 5, 0, -2, -3, 1}, nums2 = {5};
cout << obj.subarraysDivByK(nums1, 5); // expect: 7
cout << obj.subarraysDivByK(nums2, 9); // expect: 0
return 0;
}
|