Maximum subset pairwise not divisible by $K$

Problem Detail: 

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?

Asked By : manduinca

Answered By : emab

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 <K/2, ~r_2 \geq K/2~~~~~~ (r_1 \neq r_2,~\text{w.l.g.}~r_1 < r_2).$$

The third concept that you need to consider is that, if the sum of two numbers $r_1 \neq r_2$ is $K$, they both deviate from $\lceil K/2 \rceil -1$ by a certain $k \leq \lceil K/2 \rceil$, i.e.,

$$r_1 + r_2 = K ~~~\Rightarrow~~~ \exists_{k \leq \lceil K/2 \rceil -1}~~~\text{such that}~~~ r_1 = \lceil K/2 \rceil -1 -k, ~r_2 = \lceil K/2 \rceil +k.$$

So, for evey $k$ in the third concept, you need to put either $r_1$ or $r_2$ in the solution set, but not both of them. You are allowed to put one of the numbers that are actually divisible by $K$ and if $K$ is even, you can add only one number that its remainder is $K/2$.

Therefore, here is the algorithm.

Given a set ${\cal N}=\{ n_1, n_2, \cdots, n_N \}$, let's find the solution set ${\cal S},$

1. Consider ${\cal R} = \{ r_1=(n_1 ~mod ~K), r_2=(n_2 ~mod ~K), \cdots, r_N=(n_N ~mod ~K) \}$
2. ${\cal S} \gets \emptyset$
3. for $k \gets 1$ to $\lceil K/2 \rceil -1$:
4. $\hspace{1.3em}$ if $count({\cal R},k) \geq count({\cal R},K-k)$:
5. $\hspace{2.6em}$ add all $n_i$ to ${\cal S}$, such that $r_i=k$
6. $\hspace{1.3em}$ else:
7. $\hspace{2.6em}$ add all $n_i$ to ${\cal S}$, such that $r_i=K-k$
8. add only one $n_i$ to ${\cal S}$ such that $r_i=0\hspace{1em}$// if exists
9. if $K$ is even:
10. $\hspace{1.3em}$ add only one $n_i$ to ${\cal S}$ such that $r_i=K/2\hspace{1em}$// if exists
11. Output ${\cal S}$

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57873