Non-Divisible Subset

• Time : O(n + k)
• Space : O(k)

int nonDivisibleSubset(int k, vector<int> s) {
    unordered_map<int, int> mp;
    for(auto& n : s) {
        mp[n % k]++;
    }
    int res = 0;
    for(auto& [div, freq] : mp) {
        if(div * 2 == k) res++;
        else if(div == 0) res++;
        else {
            int o = k - div;
            if(!mp.count(o)) res += freq;
            else if(div > o) continue;
            else if(div < o) res += max(freq, mp[o]);
        }
    }
    return res;
}