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?

• Could you describe your solution? Are you sure there exist better solution? Does the edit preserved your intentions? – Evil May 26 '16 at 1:55
• You can find some solutions on this link. – Gadheyan .t.s May 27 '16 at 2:26
• @Gadheyan.t.s the problem that you mentioned is a very special case of this problem. In that problem, the given set of numbers is in a form of $\{1,2,\cdots,N\}$, while here we have an arbitrary set of numbers. The problem that you mentioned can be solved in $O(1)$. – orezvani May 30 '16 at 1:37

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.

• @D.W. I assumed that $r_1 \neq r_2$. I deliberately put such assumption in order to avoid even numbers; I added the following: "w.l.g $r_1 < r_2$" – orezvani May 27 '16 at 2:02
• @D.W. It doesn't completely avoid even numbers. If you proceed, you will see why I have put such concept/lemma. Basically, for even number $K$, if the remainder of some $n_i$s are exactly $K/2$, then we are interested in only one of those $n_i$s (if we put more than one, we will violate the condition of the question). That's why, I treated all such $n_i$s with that condition separately. – orezvani May 27 '16 at 2:28
• @D.W. I put w.l.g. for $r_1 < r_2$. I think that was really unnecessary but I put it just for the matter of conventions. – orezvani May 27 '16 at 2:30
• OK, I see what you mean now! Thanks for explaining. – D.W. May 27 '16 at 2:32

Consider a set S of size n containing all distinct natural numbers. We have to form the maximal subset from this set . We use a basic modulus property and add a few deductions to it to solve the problem. I hope it is helpful for you all.

For any two natural numbers N1 and N2 : (N1+N2)mod(K)=(R1+R2)mod(K) where R1=N1modK and R2=N2%K. 1. If we (N1+N2)modK=0 it means (R1+R2)%K=0. 2. That means R1+R2 must equal either K,2K,3K.... 3. But R1 lies between 0 & K-1 and so does R2 , which means their sum can't exceed K-1+K-1 = 2(K-1). 4. From 2 and 3 we can conclude that R1 + R2 must be equal to K. 5. Further if R1+R2 =K that means either both of them must be equal to K/2 (only possible if K is even) or one of them must be lesser than floor[K/2] and one greater than the same. 6. Suppose R1=T and R2=K-T , if we take any number N1 from S whose remainder is R1 and any number N2 from S whose remainder is R2 then their sum will be divisible by K. Therefore the Solution subset can have either those numbers with remainder R1 or those with remainder R2 but not both .

Now Suppose we construct an Array R of size K with index 0 through K-1 , The element in each index denoting the number of numbers in the set S with remainder (on division with K ) equal to the index number. We cant have more than 2 numbers with their remainder 0 as their sum would be divisible by K therefore we must initialise our counter with min(R[0],1). For T=1 to T

The code for the same algorithm in C++ is as shown below:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {

int n,k;
cin>>n>>k;
vector <int> a(n);
vector <int> r(k,0);
for(int i=0;i<n;i++)
{
cin>>a[i];
r[a[i]%k]++;
}
int ctr=min(1,r[0]);
for(int a=1;a<(k/2+1);a++)
{
if(a!=k-a)
ctr+=max(r[a],r[k-a]);
}
if(k%2==0&&r[k/2]!=0)
ctr++;
cout<<ctr;
return 0;
}

• Could you translate your code into pseudocode? – Evil Jan 28 '17 at 19:49
• 1. Read k,n 2. Make two arrays A and R of size n and k 3. i=0 , ctr=0, a=1 4. while(i<n) do read A[i] R[A[i]%k]++ i=i+1 endwhile 5. ctr = minimum(1,R[0]) 6. while(a<k/2+1) do if(a!=k-a) ctr= ctr+maximum(R[a],R[k-a]) endif a=a+1 endwhile 7. if(k gives 0 remainder when divided by 2 and R[k/2] is non zero ) ctr=ctr+1 8. print ctr 9. End – Dhruva Bhagdikar Feb 4 '17 at 13:58
• I have meant in the post, by using edit, sorry for inconvenience and thank you for the pseudocode. – Evil Feb 4 '17 at 14:58

I tried translating to C# code, the first to only count the size of the subset array and another including the entire (hash)subset.

Count:

static int nonDivisibleSubset(int k, int[] S)
{
var r = new int[k];

for (int i = 0; i < S.Length; i++)
r[S[i] % k]++;

int count = Math.Min(1, r[0]);

if (k % 2 == 0 && r[k / 2] != 0)
count++;

for (int j = 1; j <= k / 2; j++)
{
if (j != k - j)
count += Math.Max(r[j], r[k - j]);
}

return count;
}


With subset:

static int nonDivisibleSubset(int K, int[] S)
{
var r = new HashSet<int>();
var d = S.GroupBy(gb => gb % K).ToDictionary(Key => Key.Key, Value => Value.ToArray());

for (int j = 1; j <= K / 2; j++)
{
var c1 = d.GetValueOrDefault(j, new int[0]);
var c2 = d.GetValueOrDefault(K - j, new int[0]);

if (c1.Length == c2.Length) continue;

r.UnionWith(c1.Length > c2.Length ? c1 : c2);
}

if (d.ContainsKey(0))

if (K % 2 == 0 && d.ContainsKey(K / 2))

return r.Count;
}

• This isn't a coding site. – Yuval Filmus Aug 12 '18 at 3:26
• is this a math site? – BigChief Aug 12 '18 at 7:18
• The exact extent of the site is hard to define. You can look around to see which questions get closed and which don't. – Yuval Filmus Aug 12 '18 at 12:12
• My intent was to add some more depth to the code already posted, also the latter code block returns a subset which explicitly maximizes the complete subset instead of only returning the size of the subset. Hopefully this is helpful to anyone trying to understand the problem at hand. Also I hope to receive feedback on correctness. Posting code or mathematical equations has some equivalence? – BigChief Aug 12 '18 at 14:55
• Posting code is usually frowned upon. We prefer pseudocode or a textual description. – Yuval Filmus Aug 12 '18 at 16:54