Dev SHARMA - 4 months ago 262x
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?

``````# 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
``````
Source (Stackoverflow)