# Non-Divisible Subset Hackerrank problem solution coderinme

##### Solution of Non-Divisible Subset Hackerrank problem

Given a set, S, of n distinct integers, print the size of a maximal subset, S’, of S where the sum of any 2 numbers in S’ is not evenly divisible by k.
Input Format

The first line contains 2 space-separated integers, n and k, respectively.
The second line contains n space-separated integers (we’ll refer to the ith value as ai) describing the unique values of the set.

Constraints

• 1<=k<=10
• 1<=n<=10^5
• 1<=ai<=10^9
• All of the given numbers are distinct.

Output Format

Print the size of the largest possible subset (S’).

Sample Input

4 3
1 7 2 4

Sample Output

3

#### Explanation

The largest possible subset of integers is S’={1,7,4}, because no two integers will have a sum that is evenly divisible by k=3:

1+7=8, and 8 is not evenly divisible by 3.
1+4=5, and 5 is not evenly divisible by 3.
4+7=11, and 11 is not evenly divisible by 3.
The number 2 cannot be included in our subset because it will produce an integer that is evenly divisible by k=3 when summed with any of the other integers in our set:

1+2=3, and 3/3=1(remainder 0).
4+2=6, and 6/3=2(remainder 0).
7+2=9, and 9/3=3(remainder 0).
Thus, we print the length of S’ on a new line, which is 3.

#### Solution in C++

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

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n,k,i,c=0;
cin>>n>>k;
int arr[n];
for(i=0;i<n;i++) {
cin>>arr[i];
}
int b[k];
for(i=0;i<k;i++) {
b[i]=0;
}
for(i=0;i<n;i++) {
b[arr[i]%k]+=1;
}
c=min(b[0],1);
for(i=1;i<k/2+1;i++) {
if(i!=k-i) {
c+=max(b[i],b[k-i]);
}
}
if(k%2==0) c++;
cout<<c;
return 0;
}```

#### Solution in Python

``````rr = raw_input
rrM = lambda: map(int,rr().split())
N,K = rrM()
A = rrM()
S = [0 for _ in xrange(K)]
for i in A: S[i%K] += 1
ans = 0
for p in xrange(K/2 + 1):
q = (K-p)%K
if p==q: ans += 1 if S[p] else 0
else: ans += max(S[p],S[q])
print ans``````

#### Solution in java

``````import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int a[] = new int[n];
int cnts[] = new int[k];
for(int a_i=0; a_i < n; a_i++){
a[a_i] = in.nextInt();
cnts[a[a_i]%k]++;
}
int cnt = 0;
for (int i=1;i<=k/2;i++) {
if (2*i!=k) {
cnt += Math.max(cnts[i],cnts[k-i]);
}
}
if (k%2==0) {
if (cnts[k/2]>0) {
cnt ++;
}
}
if (cnts[0]>0) {
cnt ++;
}
System.out.println(cnt);

}
}``````

#### Solution in C

``````#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main(){
int n;
int k;
scanf("%d %d",&n,&k);

int count[k];
for (int i = 0; i < k; i++) {
count[i] = 0;
}

for(int i = 0; i < n; i++){
int a;
scanf("%d",&a);
count[a % k]++;
}

int max = 0;
for (int i = 0; i <= k/2; i++) {
if (i == 0 || i == k - i) {
if (count[i] >= 1) {
max += 1;
}
} else {
max += count[i] > count[k-i] ? count[i] : count[k-i];
}
}
printf("%d\n",max);

return 0;
}
``````

### hasectic

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi