Practice › Hashing & Two Pointers
Subarray Sums Divisible by K
Medium · Hashing & Two Pointers · Asked at Amazon, Microsoft, Twilio, Goldman Sachs
Count the non-empty subarrays whose sum is divisible by k.
Input
First line: n k. Second line: n integers.
Output
The number of such subarrays.
Constraints
- 1 ≤ n ≤ 10^5
- -10^4 ≤ a[i] ≤ 10^4
- 2 ≤ k ≤ 10^4
Two prefix sums with the same remainder mod k bound a valid subarray. Watch out: in C++/Java, % of a negative number is negative — normalise it.
Example 1
Input
6 5 4 5 0 -2 -3 1
Output
7
Example 2
Input
1 9 5
Output
0
Hints
- sum(j+1..i) is divisible by k exactly when prefix[i] and prefix[j] have the same remainder mod k.
- Count remainders as you go. Normalise negative remainders: ((x % k) + k) % k.
Approach
Keep cnt[rem] = how many prefix sums so far have remainder rem, starting with cnt[0] = 1 (the empty prefix). For each new prefix remainder m, every earlier prefix with the same remainder ends a valid subarray here, so add cnt[m] and then increment it. In C++/Java, % keeps the sign of the dividend, so fix it with ((p % k) + k) % k.
Complexity: O(n + k) time · O(k) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<long long> cnt(k, 0);
cnt[0] = 1;
long long p = 0, ans = 0, x;
for (int i = 0; i < n; i++) {
cin >> x;
p += x;
int m = ((p % k) + k) % k;
ans += cnt[m]++;
}
cout << ans << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, k, a = data[0], data[1], data[2:]
cnt = [0] * k
cnt[0] = 1
p = ans = 0
for x in a:
p += x
m = p % k # Python's % is never negative for k > 0
ans += cnt[m]
cnt[m] += 1
print(ans)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
long[] cnt = new long[k];
cnt[0] = 1;
long p = 0, ans = 0;
for (int i = 0; i < n; i++) {
p += sc.nextLong();
int m = (int) (((p % k) + k) % k);
ans += cnt[m]++;
}
System.out.println(ans);
}
}Solve Subarray Sums Divisible by K online · All practice problems