// Write your code here int arr[]=new int[k]; for(int i=0;i

int max=Math.min(arr[0],1);

for(int i=1;i<=k/2;i++) { if(i!=k-i) { max+=Math.max(arr[i],arr[k-i]); } else { max++; } } return max;

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)