# 974. Subarray Sums Divisible by K

Given an array `A` of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by `K`.

Example 1:

``````Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
``````

Note:

1. `1 <= A.length <= 30000`
2. `-10000 <= A[i] <= 10000`
3. `2 <= K <= 10000`

``````class Solution {
public:
int subarraysDivByK(vector<int>& A, int K) {
int res = 0, sum = 0;
unordered_map<int, int> m{{0, 1}};
for (int num : A) {
sum = (sum + num % K + K) % K;
res += m[sum];
++m[sum];
}
return res;
}
};
``````

``````class Solution {
public:
int subarraysDivByK(vector<int>& A, int K) {
int res = 0, sum = 0;
vector<int> cnt(K);
cnt[0] = 1;
for (int num : A) {
sum = (sum + num % K + K) % K;
res += cnt[sum];
++cnt[sum];
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/974

Subarray Sum Equals K

Make Sum Divisible by P

https://leetcode.com/problems/subarray-sums-divisible-by-k/

https://leetcode.com/problems/subarray-sums-divisible-by-k/discuss/217985/JavaC%2B%2BPython-Prefix-Sum

https://leetcode.com/problems/subarray-sums-divisible-by-k/discuss/217980/Java-O(N)-with-HashMap-and-prefix-Sum

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation