# HackerRank Non-Divisible Subset problem solution

In this HackerRank Non-Divisible Subset problem you have Given a set of distinct integers, print the size of a maximal subset of S where the sum of any 2 numbers in S' is not evenly divisible by k.

## Problem solution in Python programming.

```from collections import defaultdict

n, k = [int(item) for item in input().strip().split()]
S = [int(item) for item in input().strip().split()]
mods = [item % k for item in S]
freqs = defaultdict(int)
for elem in mods:
freqs[elem] += 1
total = 0
for key, val in freqs.items():
if val == 0:
continue
if key == 0:
total += 1
elif (k - key) == key:
total += 1
elif key > (k - key):
if (k - key) in freqs:
total +=  max([val, freqs[k - key]])
else:
total += val
elif key < (k - key):
if (k - key not in freqs):
total += val

print(total)```

## Problem solution in Java Programming.

```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[k];
for(int i=0; i < n; i++){
int ai = in.nextInt();
a[ai % k]++;
}
int count = 0;
for (int i = 1; i < (k + 1) / 2; ++i) {
count += Math.max(a[i], a[k - i]);
}
if (k % 2 == 0) {
count += a[k / 2] > 0 ? 1 : 0;
}
count += a[0] > 0 ? 1 : 0;

System.out.println(count);
}
}```

### Problem solution in C++ programming.

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

int main() {
int n, k; cin >> n >> k;
vector<int> q(k);
for (int i = 0; i != n; ++i) {
int x; cin >> x;
q[x % k] += 1;
}
int rv = min(1, q[0]);
for (int i = 1; 2*i <= k; ++i) {
int j = (k - i) % k;
if (i == j) {
rv += min(1, q[i]);
} else {
rv += max(q[i], q[j]);
}
}
cout << rv << '\n';
return 0;
}```

### Problem solution in C programming.

```#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
int n;
int k;
int a[101] = {};
scanf("%d", &n);
scanf("%d", &k);
for (int i = 0; i < n; i++) {
int tmp;
scanf("%d", &tmp);
a[tmp % k]++;
}
int count = 0;
if (a[0] > 0)
count++;
if (k % 2 == 0 && a[k / 2] > 0)
count++;
for (int i = 1, j = k - 1; i < j; i++, j--) {
if (a[i] > a[j])
count += a[i];
else
count += a[j];
}
printf("%d\n", count);
return 0;
}```

### Problem solution in JavaScript programming.

```function processData(input) {
var temp = input.split('\n');
var nk = temp[0].split(' ').map(Number), n = nk[0], k = nk[1];
var arr = temp[1].split(' ').map(Number);
var factorArray = Array(k).fill(0);
for (let i = 0; i < n; i += 1) {
factorArray[arr[i] % k] += 1;
}
let size = 0;

for (let i = 0; i < Math.floor(k/2)+1; i += 1) {
if (i == 0 || k == i * 2) {
size += (factorArray[i] != 0) ? 1 : 0;
} else {
size += Math.max(factorArray[i], factorArray[k - i]);
}
}
console.log(size);
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});

process.stdin.on("end", function () {
processData(_input);
});```