This initially appears difficult to solve in reasonable time complexity. After further thought, I think this can be done on O(n) with a few considerations. This is supposed to be an "easy" problem, so I'll provide some algorithm guidance here.

For any number K, the sum of 2 values (A & B) is evenly divisible by K if the sum of the remainders of A/K + B/K is K. (There is also a special case where both A & B are evenly divisible, giving a sum of 0.)

For any such remainder, there is 1 and only 1 other remainder value which will make a sum divisible by K.

Example: with K of 5, remainder pairs are 1+4 & 2+3. Given the numbers with a remainder of 1, they can't be paired with ANY of the numbers with remainder 4 (and vice versa). So, for the number of values in the resultant set, choose the larger of values with remainder 1 vs. values with remainder 4. Choose the larger set of remainder 2 vs remainder 3.

For the special case where remainder is 0, given the set of all values which are individually divisible by K, they can't be paired with any others. So, at most 1 value which is evenly divisible by K can be added to the result set.

For even values of K, the equal remainder is simular to the 0 case. For K = 6, pairs are 1+5, 2+4, 3+3. For values with remainder 3, at most one value can be added to the result set.

here's the logic complete which follows BigO(n) complexity of the algorithm suppose let's say u give input 10 13 where K=13 and the values are : 2375782 21836421 2139842193 2138723 23816 21836219 2948784 43864923 283648327 23874673.

Now the main logic behind this is if:

(a+b)%K=0(means evenly divisible) then (a%k+b%K=K)

Hence, we take first take the remainders of all the input integers by dividing them with K, In this case we divide all the integers by K=13 which gives us the following set of remainders:

6 9 8 2 0 2 7 11 1 4

now look carefully in the remainder set,

i.) 11+2=13=K thus, we cannot have both 11 and 2 , we must select one of them based on the higher frequency, in this case 2 has a higher frequency than 11 so SELECT all the 2s

ii.) 7+6=13=K thus, we cannot have both 7 and 6 , we must select one of them based on the higher frequency, in this case 6 and 7 both have equal frequencies so select any one of them, let's say(we select 6)

iii.) 9+4=13=k thus, we cannot have both 9 and 4 , we must select one of them based on the higher frequency, in this case 9 and 4 both have equal frequencies so select any one of them, let's say(we select 9)

now we are left with remainders 1,8,0

so the final subset of remainders comes out to be

[6,9,2,2,1,8,0]
the length of this subset is the answer which is"7"

Hope this helps:)

also there are two special cases

1.)if k=0 then return 1 since none will be divisible

2.)if k=1 then return 1 since all the numbers will be divisible

I have done with Java. I have added some comments. I hope it will be clear for everyone

// Complete the nonDivisibleSubset function below.
    static int nonDivisibleSubset(int k, int[] S) {
        // In maths. if (a + b) % k = 0 => then ((a % k) + (b % k)) % k = 0
        // Example: (5 + 7) % 6 = 0 => then (5 % 6) + (7 % 6) > (5 + 1) % 6 = 0

        // Solution: Find remainder of each element in the array.
        // then, choose max element from the pair which together can able to be divided by k. If one pair is "i" then other pair will be "k-i"
        // For example: S = {2, 3, 7, 8, 12} and k = 5.
        // Now we have 3 numbers whose remainder 2 => ( 2 % 5 = 2, 7 % 5 = 2, 12 % 5 = 2)
        // and also we have 2 numbers whose remainder 3 => (3, 8)
        // Right now we have to choose one of the element from that pair (3, 2) (where 3 > numbers 2, 7, 12 && 2 > numbers 3, 8)
        // Because of the problem, we will choose the max which is 3.

        int[] remainderArr = new int[k];
        // find remainder of each element in the array S
        // For example k = 4, S = {0, 5, 7, 10} => remainderArr will be: {0, 1, 1, 1}
        // where each index represents remainder. For example remainderArr[2] = 1 means
        // that there is 1 number whose remainder 2 after divided 4. (10 % 4 = 2)
        for (Integer each : S) {
            remainderArr[each % k]++;
        }

        // After getting each remainder, index 0 (actually remainder 0) is a special case
        // Think of it like this:
        //      1. There will be no element such as k - 0 = k. (remainderArr[k] will give us ArrayIndexOutOfBoundsException)
        //      2. If there are 2 elements in remainderArr[0], we have to choose only 1, otherwise, we can sum up 2 or more
        //         zeros, then non-sub divisible set could be divisible by k.
        int zeroRemainder = remainderArr[0];

        // That's why, our initial subset size is 1, if there is a zero remainder,
        //                                           otherwise it is 0
        int maxNumberOfDivisibleSet = zeroRemainder > 0 ? 1 : 0;

        // Another thing is that pair which is itself. That's means, let's say k = 4, therefore pair of remainderArr[2]
        // will also be remainderArr[2]( i = 2 then, k - i = 2). Thus, we have to choose only 1 element from that pair (or we should increment
        // the result number just 1)
        // if condition "i != k - i" will handle this situation.
        for (int i = 1; i <= (k / 2); i++) {
            if (i != k - i)
                maxNumberOfDivisibleSet += Math.max(remainderArr[i], remainderArr[k - i]);
            else
                maxNumberOfDivisibleSet ++;
        }

        return maxNumberOfDivisibleSet;
    }

Cool question - it was fun to learn some number theory. Not sure I'd rate this as "easy" though!

This problem is really difficult if you don't see the trick that you can just look at remainders because A+B is divisible by k iff (A%k)+(B%k)=k. I didn't get that at first, so I tried to brute force it by constructing all the subsets of each size from 2 to n and testing if each set is valid. This was correct, but very inefficient. Especially when you consider that there will be 2^n different subsets! Don't try it this way. You just have to see the trick (I don't really like problems like this for that reason).