We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Non-Divisible Subset
  5. Discussions

Non-Divisible Subset

  • jjr20060326
     + 0 comments

    In the comments section was my first solution but the execution time was too long.

    def nonDivisibleSubset(k, s):
    # import itertools
    
    # for r in range(len(s), 0, -1):
    #     for c in itertools.combinations(s, r):
    #         if all(sum(comb) % k != 0 for comb in itertools.combinations(c, 2)):
    #             return len(c)
    # return 0 
    
    from collections import Counter
    
    freq = Counter(num % k for num in s)

    count = min(freq.get(0, 0), 1)

    for i in range(1, (k // 2) + 1):
        if i == k - i:
            count += 1
        else:
            count += max(freq.get(i, 0), freq.get(k - i, 0))

    return count