Non-Divisible Subset

Given a set of distinct integers, print the size of a maximal subset of S where the sum of any 2 numbers in  is not evenly divisible by k.

Example:

Input:  n = 4, k = 3, s = {1, 7, 2, 4}
Output: 3

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int nonDivisibleSubset(int k, vector<int> s)
{

    vector<int> rem(k);

    for (int i = 0; i < s.size(); i++)
    {
        rem[s[i] % k]++;
    }
    int zero = rem[0];

    int res = zero > 0 ? 1 : 0;
    for (int i = 1; i <= (k / 2); i++)
    {
        if (i != k - i)
            res += max(rem[i], rem[k - i]);
        else
            res++;
    }

    return res;
}
int main()
{

    int n = 4, k = 3;

    vector<int> s = {1, 7, 2, 4};

    cout << nonDivisibleSubset(k, s) << "\n";

    return 0;
}