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

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.

• Welcome to CS.SE! 1. Something's missing after "Then, it is said:". 2. What's your question, and what have you tried to try to work out the answer on your own? – D.W. Jul 15 '16 at 18:49
• The question is complete. I dont understand the logic of pairing elements from bucket 2 and bucket 3. – user3426358 Jul 15 '16 at 18:51
• I suggest editing your post to ask a specific question. This is a question-and-answer site, so it's helpful to be really specific about what you want answered. And, again, tell us your thoughts and what efforts you've made to answer the question on your own (you should be making those kinds of efforts before asking here). – D.W. Jul 15 '16 at 19:29
• Your problem mentions an array a, but it's not actually used anywhere. So can you please restate this problem with a bit more care. – gnasher729 Jul 15 '16 at 20:03
• Question hasn't been changed. Answer: Infinitely many pairs, for example the infinitely many pairs (0, k), (0, 2k), (0, 3k) etc. and many, many others. – gnasher729 Jul 17 '16 at 12:25

## 1 Answer

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.