Dev SHARMA Dev SHARMA - 6 months ago 349
Python Question

Non Divisible subset in python

I have been given a set S, of n integers, and have to print the size of a maximal subset S' of S where the sum of any 2 numbers in S' are not evenly divisible by k.

Input Format

The first line contains 2 space-separated integers, n and k, respectively.
The second line contains n space-separated integers describing the unique values of the set.

My Code :

import sys


n,k = raw_input().strip().split(' ')
n,k = [int(n),int(k)]
a = map(int,raw_input().strip().split(' '))
count = 0


for i in range(len(a)):
for j in range(len(a)):
if (a[i]+a[j])%k != 0:
count = count+1

print count


Input:

4 3
1 7 2 4


Expected Output:

3


My Output:

10


What am i doing wrong? Anyone?

Answer
# given k, n and a as per your input.
# Will return 0 directly if n == 1
def maxsize(k, n, a):
    import itertools
    while n > 1:
        sets = itertools.combinations(a, n)
        for set_ in sets:
            if all((u+v) % k for (u, v) in itertools.combinations(set_, 2)):
                return n
        n -= 1
    return 0