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

  • wilmer_henao
     + 3 comments

    I'm wondering the same thing. He adds that 1 at the end if k%2. But how do you guarantee that it exists?. I think the right code should be:

    n, k = map(int,raw_input().strip().split(" "))
arr = map(int,raw_input().strip().split(" "))
residuals = [i %k for i in arr]
counter = [0] * k
for r in residuals:
    counter[r] += 1
    
# max one element with residual 0
c = min(counter[0], 1)

for i in range(1, (k//2)+1):
    if i != k-i:
        c += max(counter[i], counter[k-i])
    else:
        c += min(counter[i], 1)
    
print(c)

    But somehow his code gets lucky and passes all cases.