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.
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
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.
- All of the given numbers are distinct.
Print the size of the largest possible subset ().
4 3 1 7 2 4
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))
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.