LeetCode Solutions
974. Subarray Sums Divisible by K
Time: Space:
class Solution {
public:
int subarraysDivByK(vector<int>& A, int K) {
int ans = 0;
int prefix = 0;
vector<int> count(K);
count[0] = 1;
for (int a : A) {
prefix = (prefix + a % K + K) % K;
ans += count[prefix];
++count[prefix];
}
return ans;
}
};
class Solution {
public int subarraysDivByK(int[] A, int K) {
int ans = 0;
int prefix = 0;
int[] count = new int[K];
count[0] = 1;
for (int a : A) {
prefix = (prefix + a % K + K) % K;
ans += count[prefix];
++count[prefix];
}
return ans;
}
}
class Solution:
def subarraysDivByK(self, A: List[int], K: int) -> int:
ans = 0
prefix = 0
count = [1] + [0] * (K - 1)
for a in A:
prefix = (prefix + a) % K
ans += count[prefix]
count[prefix] += 1
return ans