## Hackerrank - Non-Divisible Subset Solution

Given a set of distinct integers, print the size of a maximal subset of where the sum of any numbers in is *not* evenly divisible by .

For example, the array and . One of the arrays that can be created is . Another is . After testing all permutations, the maximum length solution array has elements.

**Function Description**

Complete the *nonDivisibleSubset* function in the editor below. It should return an integer representing the length of the longest subset of meeting the criteria.

nonDivisibleSubset has the following parameter(s):

*S*: an array of integers*k*: an integer

**Input Format**

The first line contains space-separated integers, and , the number of values in and the *non* factor.

The second line contains space-separated integers describing , the unique values of the set.

**Constraints**

- All of the given numbers are distinct.

**Output Format**

Print the size of the largest possible subset ().

**Sample Input**

```
4 3
1 7 2 4
```

**Sample Output**

```
3
```

**Explanation**

The sums of all permutations of two elements from are:

```
1 + 7 = 8
1 + 2 = 3
1 + 4 = 5
7 + 2 = 9
7 + 4 = 11
2 + 4 = 6
```

We see that only will not ever sum to a multiple of .

### Solution in Python

```
from collections import Counter
def nonDivisibleSubset(a):
c = Counter((i%k for i in a))
count = 0
blacklist = set()
for x,y in c.most_common():
if x == k/2 or x==0:
count+=1
elif k-x not in blacklist:
count+=y
blacklist.add(x)
return count
n,k = map(int,input().split())
a = list(map(int,input().split()))
print(nonDivisibleSubset(a))
```

Algorithm explanation

Let, array S = [19,10,12,24,25,22] and k =4

First we will convert the item inside S to smallest possible numbers

```
>>> k = 4
>>> S = [19,10,12,24,25,22]
>>> S = [i%k for i in S]
>>> S
[3, 2, 0, 0, 1, 2]
```

Now we can use our new list instead of original S.

In our original list [10,12,25] [19,22,24] are the valid permutations

If we compare these values with that in new S, our possible permutations will be [2,0,1] [3,2,0]

As you can see that in both cases sum of any 2 number is not divisible by k=4.

Now we will list all the possibilities of adding any two numbers smaller than k which is divisible by k

```
1+3 = 4
2+2 = 4
0+0 = 0
```

There are 3 cases which will result in a number divisible by 4.

2+2 = 4, 0+0 =0 . It means we can never have more than one 0 or more than one 2(half of k)

1+3 =4. It means we can add as many 1 as we want unless we don't have a 3 in our list and vice versa. We just have to take the one which has more occurrence.

Suppose S = [1,2,2,0,0,0,0,1,1,1,3]

Since we can't include more than one 0 and one 2. We will take only one each of 0 and 2. And since 1 occurs more times than 3.. We will sacrifice 3 and include all 1s in our array.

[0,2,1,1,1,1]