Non-Divisible subset. (Hackerrank question).

Question

An array and k is given. We have to find a subset such that no pair in the subset divisible by k and the length of the subset must be maximum..

Input-[1,7,3,2] and k=3

Output-3 because the subset based upon the condition is [1,7,3].where the sum of any two is not divisible by k.

Answer 1

I would search for divisible pairs.
Full sum = 13
Multiples of 3 <= 13:
3, 6, 9, 12

1 - 3 neg
7 - 3 = 4 -> list don't cotains 4
3 - 3 = 0 -> list don't cotains 0
3 - 2 = 1 -> list contains 1

Do this for all multiples to find the pairs:
1 + 2 = 3 & 2 + 7 = 9
-> 2 is part of both pairs -> remove 2