The optimal algorithm needed to find pairs divisible by a given integer k

Question

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

I do not know the boundaries on n and k. So, for simplicity, suppose that n and k are not very large.

Needless to say, give the best possible solution. (I know the naive method :-)! )

Answer 1

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

So, if k is small enough, you can just count how many numbers each possible remainder has and calculate the number of pairs from that. Assuming k > 0 and all non-negative integers

 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[ki]; } if (k == 2*i) { combs += counts[i]*(counts[i] - 1)/2; } return combs; } 

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

Answer 2

In addition to what Daniel Fisher says, if k is very large, you can sort the numbers mod k and then scroll through the sorted list from both ends (after processing with values ​​0 mod k) towards the middle (k / 2 mod k). This is O (n log n), which is better than O (n ^ 2), considering that your naive algorithm is really naive.