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]