Find Divisible Sum Pairs in an array in O(n) time

Question

You are given an array of n integers a0, a1, .. an and a positive integer k. Find and print the number of pairs (i,j) where i<j and i+j is evenly divisible by k (Which is i+j % k == 0). This problem has been taken from Hackerrank.

We need a solution in O(n) time.

An explanation is that we can do this by separating elements into buckets depending on their mod k. For example, you have the elements: 1 3 2 6 4 5 9 and k = 3

mod 3 == 0 : 3 6 9
mod 3 == 1 : 1 4
mod 3 == 2 : 2 5

Now, you can make pairs like so:

Elements with mod 3 == 0 will match with elements with (3 - 0) mod k = 0, so other elements in the mod 3 == 0 list, like so: (3, 6) (3, 9) (6, 9)

Further:

There will be n * (n - 1) / 2 such pairs, where n is length of the list, because the list is the same and i != j. Elements with mod 3 == 1 will match with elements with (3 - 1) mod k = 2, so elements in the mod 3 == 2 list, like so: (1, 2) (1, 5) (4, 2) (4, 5)

It makes sense that (3, 6) (3, 9) (6, 9) ( all items in the 0th bucket be paired) since (a + b)% k = 0 = a % k + b % k.

What isnt clear is how the other pairs (1, 2) (1, 5) (4, 2) (4, 5) were generated by combination of elements in the 1st (mod 3 == 1) and the 2nd (mod 3 == 2) bucket and why would there be n * (n - 1) / 2 pairs.

Answer 1

Consider in your example the set $S_1=\{1, 4\}$ and the set $S_2=\{2,5\}$. Let $n_1 = 2$ and $n_2=2$, the sizes of sets $S_1$ and $S_2$. All of the elements $x\in S_1$ satisfy $x\equiv 1\pmod 3$ and so are of the form $x=3s+1$ for some $s$. Similarly all $y\in S_2$ are of the form $y=3t+2$ so $x+y=3s+1+3t+2=3(s+t+1)$, which is divisible by 3. The number of such pairs is $n_1\cdot n_2$: pick one element, $x$, from $S_1$ and one element, $y$, from $S_2$ to form the pair $(x, y)$, rearranging, if necessary so that the first element is less than the second. In sum, there will be $n_1\cdot n_2=2\cdot 2$ pairs: $(1, 2), (1, 5), (4, 2), (4, 5)$, which, after arranging the pairs in component orders, gives $(1, 2), (1, 5), (2, 4), (2, 5)$ (your highlighted quote didn't do that).

For a general $k$, then, you'll have sets $S_i$, for $i=1, \cdots k-1$ (ignoring $S_0$ for the moment), so if $n_i$ represents the size of $S_i$, you'll have pairs $(x,y)$ where $x\in S_i$ and $y\in S_{k-i}$. The number of such pairs is $n_1\cdot n_{k-1}+n_2\cdot n_{k-2}+\dotsc$.

[You have to be a bit careful, since, first, the sum only should include those products $n_i\cdot n_{k-i}$ for which $i<k-i$, and second, you'll have to account for the cases where $i$ and $k-i$ are equal. You'll also have to deal with the pairs you get from $S_0$, which have to be counted differently.]

I'd suggest ignoring the sentence where $n(n-1)/2$ appears: it's true but irrelevant.