# Non – Divisible Subset – HackerRank Solution

In this post, we will solve Non – Divisible Subset HackerRank Solution. This problem (Non – Divisible Subset) is a part of HackerRank Ruby series.

Contents

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.

Example
Â S = [19, 10, 12, 10, 24, 25, 22] k = 4

One of the arrays that can be created isÂ S‘[0] = [10, 12, 25]. Another isÂ S‘[1] = [19, 22, 24]. After testing all permutations, the maximum length solution array hasÂ 3Â elements.

Function Description

Complete the nonDivisibleSubset function in the editor below.

nonDivisibleSubset has the following parameter(s):

• int S[n]: an array of integers
• int k: the divisor

Returns

• int:Â the length of the longest subset ofÂ SÂ meeting the criteria

## Input Format

The first line containsÂ 2Â space-separated integers,Â nÂ andÂ k, the number of values inÂ SÂ and theÂ nonÂ factor.
The second line containsÂ nÂ space-separated integers, each anÂ S[i], the unique values of the set.

## Constraints

• 1 <= n <= 105
• 1 <= k <= 100
• 1 <= S[i] <= 109
• All of the given numbers are distinct.

Sample Input

``````STDIN    Function
-----    --------
4 3      S[] size n = 4, k = 3
1 7 2 4  S = [1, 7, 2, 4]``````

Sample Output

``3``

Explanation

The sums of all permutations of two elements fromÂ S = {1, 7, 2, 4}Â are:

OnlyÂ S‘ = {1, 7, 4}Â will not ever sum to a multiple ofÂ k = 3.

## Solution – Non – Divisible Subset – HackerRank Solution

### C++

```#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<pii> vii;
typedef vector<string> vs;

int main() {
int n,k;
cin >> n >> k;
vi a(n);
vi c(k);
for (int i = 0; i < n; ++i) {
cin >> a[i];
++c[a[i] % k];
}
int res = min(1, c[0]);
for (int i = 1; 2*i < k; ++i) {
res += max(c[i], c[k-i]);
}
if (k % 2 == 0) res += min(1, c[k/2]);
cout << res << endl;
return 0;
}
```

### Python

```#!/bin/python3
# try a dumb bruteforce

import sys
from itertools import combinations

def check_array(k, arr):
for el1 in arr:
test_arr = list(arr)
test_arr.remove(el1)

for el2 in test_arr:
if (el1 + el2) % k == 0:
return False
return True

def nonDivisibleSubset_brute(k, arr):
if check_array(k, arr):
return len(arr)

best = 0
for num in range(1, len(arr)):
to_remove = list(combinations(arr, num))
#print("to_remove = {}".format(to_remove))
for option in to_remove:
test_arr = list(arr)
#print("test_arr = {}".format(test_arr))
for el in option:
test_arr.remove(el)

if check_array(k, test_arr) == True:
best = max(len(test_arr), best)

return best

def nonDivisibleSubset(k, arr):
resid_cnt = [0] * k

for el in arr:
resid_cnt[el%k] += 1

res = min(1, resid_cnt[0])
for ind in range(1, (k//2)+1):
if ind != k - ind:
res += max(resid_cnt[ind], resid_cnt[k - ind])

if k % 2 == 0 and resid_cnt[int(k/2)] != 0:
res += 1

return res

if __name__ == "__main__":
n, k = input().strip().split(' ')
n, k = [int(n), int(k)]
arr = list(map(int, input().strip().split(' ')))
result = nonDivisibleSubset(k, arr)
print(result)
```

### 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) throws IOException{
new Solution().run();
}

public void run() throws IOException{
Scanner in = new Scanner(System.in);
BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
int n = in.nextInt();
int k = in.nextInt();

int[]a = new int[n];
int[]c = new int[k];

for(int i=0;i<n;i++){
a[i] = in.nextInt();
a[i]=a[i]%k;
c[a[i]]++;
}

int ans=0;
ans+=(c[0]>0)?1:0;//good if 1 exists, cannot be more
for(int i=1;i<=k-i;i++){
if(i<k-i) {
ans+=Math.max(c[i],c[k-i]);
} else {//i==k-i
ans+=(c[i]>0)?1:0;//not more possible
}
}
log.write("" +ans+"\n");

log.flush();
}
}
```

Note: This problem (Non – Divisible Subset) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.