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

  • wkusnierczyk
     + 57 comments

    You don't really need to collect the actual numbers and then use the lengths of the collections; just count the numbers and use the counts.

    Since you have already posted the implementation, here's an update:

    n, k = map(int,raw_input().strip().split(" "))
numbers = map(int,raw_input().strip().split(" "))

counts = [0] * k
for number in numbers:
    counts[number % k] += 1

count = min(counts[0], 1)
for i in range(1, k//2+1):
    if i != k - i:
        count += max(counts[i], counts[k-i])
if k % 2 == 0: 
    count += 1

print count