Replace an obvious O(n²) method with one that does a single pass.
What to build
A program that counts the pairs of positions whose numbers add up to a multiple of k, without trying every pair.
Requirements
- Count how many numbers have each remainder when divided by
k. - Work out the answer from those counts alone.
- Handle remainder 0, and remainder k/2 when
kis even, as groups that pair with themselves. - Keep the answer in a
long long.
Input
The first line has n and k. The second line has the n numbers.
Output
The number of pairs of positions i < j whose sum is divisible by k.
Constraints
1 ≤ n ≤ 1000, 1 ≤ k ≤ 1000, and each number is from 0 to 1000000.
Example
Input:
6 3
1 2 3 4 5 6
Output:
5
Why it works
If c numbers have remainder r and d have remainder k − r, there are c × d such pairs, and a group that pairs with itself gives c(c − 1) / 2. That replaces O(n²) work with O(n + k).
Examples
6 3 1 2 3 4 5 6
5
4 2 2 4 6 8
6
Hints
Hint 1
Two numbers add up to a multiple of `k` exactly when their remainders add up to 0 or to `k`.
Hint 2
Count how many numbers have each remainder. You no longer need to look at pairs of numbers.
Hint 3
Remainder 0 pairs with itself. So does remainder k/2, when `k` is even.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
long long count[1000];
int main(void) {
int n, k, x;
scanf("%d %d", &n, &k);
long long answer = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &x);
count[x % k]++;
}
answer += count[0] * (count[0] - 1) / 2;
for (int r = 1; r <= k - r; r++) {
if (r == k - r) answer += count[r] * (count[r] - 1) / 2;
else answer += count[r] * count[k - r];
}
printf("%lld\n", answer);
return 0;
}