1
$\begingroup$

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 = [0]* 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – greybeard Jan 3 '17 at 16:19
2
$\begingroup$

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}. $$

$\endgroup$
  • $\begingroup$ (While the description suggests differently, the equivalent summation is just what I'd code.) $\endgroup$ – greybeard Jan 3 '17 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.