counts = [0] * k
for el in s: counts[el%k] += 1

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

return res

The fact that the hardest part on this thing was remembering how mods work other than checking if smt is divisible xd

int nonDivisibleSubset(int k, vector<int> s) {
    vector<int> mods(k, 0);

    for (int x : s) {
        mods[x % k]++;
    }

    int count = 0;

    if (mods[0] > 0) count++;

    for (int i = 1; i <= k / 2; i++) {
        if (i == k - i) {
            count++;
        } else {
            count += max(mods[i], mods[k - i]);
        }
    }

    return count;
}

The wording "maximal subset of S" is mistaken. "Maximal" does not mean largest. It means any set that can't be extended by adding a new element of S without violating the definition of the desired subset (the non-divisibility property). The correct term is "maximum", which means largest. Again, "maximal" only means not extendible, and a maximal subset may not be a maximum subset.

Here is my thought process:

1. Definitely turn the problem into modulo -> r_map[] size k + Counting

2. Now is the fun part. I first thought it was a DP, but it was much easier. Each pair i+j = k -> choose the one with more elements

3. with i = 0 and i = k // 2 -> either 1 or 0

o(k/2)

This is a tough problem, not least because the description tacitly leads you to an exhaustive search. As you begin implementing this solution it should be clear this will take forever if the size of the set is not small. One way to reduce the size of the set it to consider the equivalence classes modulo k, instead of the elements themselves. However, this set can still have as many as k elements. The solution needs to be constructive - i.e. you must construct the largest subset. There are undoubtably faster ones, but a readable solution looks like

1. Create a hash table for equivalence classes (keys are i%k; values are arrays containing all elts with that modulo), then from this create a hash table with the same keys, but values are the lengths of the value arrays above.
2. We are only summing 2 elements at once thus only need to check pairs of our eq classes. And we know that for any i, the only elt j such that (i+j)%k = 0 is k-i. Thus we need only find which has the larger eq class: i or k-i. Find the max and sum them up.
3. be aware of k/2 (if k is even), and multiples of k. Each can have only 1 element in the set. This can be addressed in the hash table containing the lengths of the eq-classes.