Optimal Algorithm needed for finding pairs divisible by a given integer k

Question

Given n integers and an integer k, tell how many such pairs of the given n integers exist such that the sum of the two elements in the pair is divisible by k ?

I don't know the bounds on n and k. So, for the sake of simplicity, assume n and k are not very large.

It goes without saying, give as optimal solution as possible. ( I know the naive method :-) ! )

Answer 1

Whether the sum of two numbers is divisible by k only depends on their remainders modulo k.

So if k is reasonably small, you can just count how many numbers have each possible remainder and compute the number of pairs from that. Assuming k > 0 and all integers nonnegative

unsigned long long combinations(unsigned k, unsigned long long *arr, unsigned n) {
    unsigned long long counts[k] = {0};
    unsigned i;
    for(i = 0; i < n; ++i) {
        ++counts[arr[i]%k];
    }
    // number of pairs where both are divisible by k
    unsigned long long combs = counts[0]*(counts[0]-1)/2;
    for(i = 1; i < (k+1)/2; ++i) {
        combs += counts[i]*counts[k-i];
    }
    if (k == 2*i) {
        combs += counts[i]*(counts[i] - 1)/2;
    }
    return combs;
}

does the job in O(n+k) steps. If n is small and k very large, the naive algorithm is better.

Answer 2

In addition to what Daniel Fischer says, if k is very large, you can sort the numbers mod k, and then walk the sorted list from both ends (after dealing with the 0 mod k values) towards the middle (k/2 mod k). That's O(n log n), which is better then O(n^2), assuming that your naive algorithm is really naive.