You are viewing a single comment's thread. Return to all comments →
Efficient solution implemented in Python3
def nonDivisibleSubset(k, s): if k ==1: return 1 #first exception res = [x%k for x in s] #array of residues mod k recurrence = dict([(x,0) for x in range(k)]) #dict for saving recurrence of residues in array s for i in range(len(res)): recurrence[res[i]] += 1 result = 0 if recurrence[0]>0: result += 1 #Add one multiple of k, if exists if k <=3:#Two more special cases if k == 2 and recurrence[1]: result += 1 else: result += max(recurrence[1],recurrence[2]) return result for x in range(1,k//2): result += max(recurrence[x],recurrence[k-x]) if k%2 == 0 and recurrence[k/2] > 0: result += 1 else: result += max(recurrence[k//2],recurrence[k - k//2]) return result
Seems like cookies are disabled on this browser, please enable them to open this website
Non-Divisible Subset
You are viewing a single comment's thread. Return to all comments →
Efficient solution implemented in Python3