Practice › Hashing & Two Pointers
Pairs Divisible by K
Medium · Hashing & Two Pointers
Count the pairs of indices i < j such that a[i] + a[j] is divisible by k.
Input
First line: n. Second line: n integers. Third line: k.
Output
The number of pairs.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ a[i] ≤ 10^9
- 1 ≤ k ≤ 10^5
Checking every pair is O(n²) — too slow for n = 10^5. The answer can exceed the 32-bit range.
Example 1
Input
5 1 2 3 4 5 3
Output
4
Example 2
Input
3 2 2 2 2
Output
3
Hints
- Only the remainders a[i] % k matter: (x + y) % k == 0 exactly when x % k + y % k is 0 or k.
- Scan left to right with a count of each remainder seen so far. Element x pairs with every earlier element whose remainder is (k − x % k) % k.
Approach
For each element with remainder r = x % k, a partner needs remainder (k − r) % k. The extra % k makes remainder 0 pair with 0. Walk the array once. First add count[(k − r) % k], the earlier elements that pair with this one, then do count[r]++. Counting before inserting means every pair i < j is counted exactly once. With n = 10^5 the answer can reach about 5 × 10^9, so use a 64-bit counter.
Complexity: O(n + k) time · O(k) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
long long k;
cin >> k;
vector<long long> cnt(k, 0);
long long pairs = 0;
for (long long x : a) {
long long r = x % k;
pairs += cnt[(k - r) % k];
cnt[r]++;
}
cout << pairs << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a, k = data[1 : n + 1], data[n + 1]
cnt = [0] * k
pairs = 0
for x in a:
r = x % k
pairs += cnt[(k - r) % k]
cnt[r] += 1
print(pairs)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
int k = sc.nextInt();
long[] cnt = new long[k];
long pairs = 0;
for (long x : a) {
int r = (int) (x % k);
pairs += cnt[(k - r) % k];
cnt[r]++;
}
System.out.println(pairs);
}
}