Dev SHARMA Dev SHARMA - 1 year ago 631
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


4 3
1 7 2 4

Expected Output:


My Output:


What am i doing wrong? Anyone?

Answer Source
# 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
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download