Maximum subset pairwise not divisible by $K$

I have a set of numbers, and want to calculate the maximum subset such that the sum of any two of it's elements is not divisible by an integer $K$.
I tried to solve this problem, but I have found the quadratic solution, which is not efficient response.

$K < 100, N < 10000$, where $N$ is the number of elements and $K$ is given constant. Is there better than quadratic solution?

Indeed there is a linear time algorithm for this. You only need to use some basic number theory concepts. Given two numbers $n_1$ and $n_2$, their sum is divisible to $K$, only if the sum of their remainder is divisible to $K$. In other words,

$$K \mid ( n_1 + n_2 ) ~~~~ \Longleftrightarrow ~~~~ K \mid \left((n_1 ~mod ~K) + (n_2 ~mod ~K)\right).$$

The second concept that you need to consider is that, the sum of two numbers $r_1 \neq r_2$ is $K$, only if one of them is strictly smaller than $K/2$ and the other is no less than $K/2$. In other words,

$$r_1 + r_2 = K ~~~\Rightarrow~~~ r_1

• ${\cal S} \gets \emptyset$

• for $k \gets 1$ to $\lceil K/2 \rceil -1$:

• $\hspace{1.3em}$ if $count({\cal R},k) \geq count({\cal R},K-k)$:

• $\hspace{2.6em}$ add all $n_i$ to ${\cal S}$, such that $r_i=k$

• $\hspace{1.3em}$ else:

• $\hspace{2.6em}$ add all $n_i$ to ${\cal S}$, such that $r_i=K-k$

• add only one $n_i$ to ${\cal S}$ such that $r_i=0\hspace{1em}$// if exists

• if $K$ is even:

• $\hspace{1.3em}$ add only one $n_i$ to ${\cal S}$ such that $r_i=K/2\hspace{1em}$// if exists

• Output ${\cal S}$

The algorithm is quite long, but the idea is very simple.

StackExchange Computer Science Q#57873, answer score: 15