# Sum of two elements in set evenly divisible by k

I have gone through this particular problem in hackerrank.

You are given an array of $n$ integers, $a_0, a_1, a_2 , \ldots, a_n$, and a positive integer $k$. Find and print the number of pairs $(i, j)$ such that $i < j$ and $a_i + a_j$ is evenly divisible by $k$.

I wanted to make this work in $O(n)$ time. After lots of searching I found a solution online.

a = [1, 3, 2, 6, 1, 2]
k = 3
m = * k
count = 0
for i in a:
rem = i % k
com = (k - rem) % k
count += m[rem]
m[com] += 1
print(rem, com, count, m)
print(count)


This particular snippet works in $O(n)$ time. But I am having a hard time understanding whats going on mathematically, especially with rem and com variables.

Can anyone please explain me the aspect(mathematical) behind it.

• I wanted to make this work in O(n) time. After lots of searching I found a solution online. there's a funny approach promising to be neither fun nor inducing insight. – greybeard Jan 3 '17 at 16:19

This solution actually works in time $O(n+k)$. The idea is to maintain an array $m_0,\ldots,m_{k-1}$, where $m_r$ is the number inputs seen so far which leave a remainder of $r$ after division by $k$. When we see a new input which leaves a remainder of $r$ after division by $k$, we count $m_{k-r}$ new pairs (where $m_k = m_0$), and then update the array $m$.
A simpler solution is to first compute a histogram $m_0,\ldots,m_{k-1}$, where $m_r$ is the number of inputs in total which leave a remainder of $r$ after division by $k$. For each pair $s+t = k$, we count $m_sm_t/2$ pairs, and for $s=t=0$, we count $m_0(m_0-1)/2$ pairs (exercise), for a total of $$\frac{m_0(m_0-1)}{2} + \sum_{s=1}^{\lfloor k/2 \rfloor} \frac{m_sm_t}{2}.$$