In this problem we are asked:

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

###Code My idea is that the only relevant part are the reminders with respect to k. Additionally, for each number there is only one number that can sum up to k. So the problem can be reduced to counting the number of numbers with the same reminder and comparing to its complement, and accumulating the one with the maximum value. Also, the numbers whose reminder is 0 or whose double is equal to k can only be counted one.

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator> 

int non_divisible_subset_size(int k, std::vector<int> v) {
    if (v.begin() == v.end()) return 0;
    // Checking the reminder allows to group different numbers which have the same influence
    std::for_each(v.begin(), v.end(), [&k](auto& x){x%=k;});
    std::sort(v.begin(),v.end());
    int max_count{0};
    // Only one of the elements with reminder 0 can be added
    if (*v.begin()== 0) ++max_count;
    // Each element has only one complement that can sum up to k
    // The complement of a number betwen 0 to k/2 is located from k/2 to k-1
    // Therefore we only need to loop from (0 to k/2]
    for(auto it_lower=std::upper_bound(v.begin(),v.end(),0);
        *it_lower <= k/2;
        it_lower=std::upper_bound(v.begin(),v.end(),*it_lower)) 
    {
       auto it_upper = std::upper_bound(v.begin(),v.end(),*it_lower);
       int count;
       if (*it_lower*2 == k) {
           count = 1;
       }
       else { 
           count = it_upper-it_lower;
       }
       int complement = k-*it_lower;
       auto it_lower_comp = std::lower_bound(v.begin(),v.end(),complement);
       auto it_upper_comp = std::upper_bound(v.begin(),v.end(),complement);
       int count_comp = count;
       if (*it_lower_comp == complement) {
           if (complement*2 == k) {
               count_comp = 1;
           } 
           else { 
               count_comp = it_upper_comp - it_lower_comp;
           }
       }
       max_count += std::max(count,count_comp);
    }
    return max_count;
}

int main() {
    int n, k; std::cin >> n >> k;
    std::vector<int> v(n);
    for(auto& e : v) std::cin >> e;
    
    int result = non_divisible_subset_size(k, v);
    std::cout << result << std::endl;
    return 0;
}

Questions

The code works, but it seems to be too slow to past the test, I'm not sure how could I optimize the speed or what is making my code so slow. I guess the slowest part is computing the reminders, maybe is not a good idea, I'm not sure. Any proposal or comment?