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.