In [this problem](https://www.hackerrank.com/challenges/non-divisible-subset/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 two numbers in it is not evenly
> divisible by _k_.


### Code 
My idea is that the only relevant part are the remainders 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 remainder and comparing to the count of its complement, and accumulating the one with the maximum value. The following picture explains the idea, for the following remainders and a value of _k_ = 5, we need to count +1 for the 0, and then add the maximum between each pair to get the total size of the maximum set.

[![enter image description here][1]][1]

Also, the numbers whose remainder is 0 and the number which is the double of _k_ can only be included once in the set.

    #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 remainder 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 remainder 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;
        v.reserve(n);
        while(n--) {
            int x; std::cin >> x;
            v.push_back(x);
        }
        
        int result = non_divisible_subset_size(k, v);
        std::cout << result << std::endl;
        return 0;
    }

### Questions
The code works and I get the correct results, but it seems to be too slow to past the tests of the challenge, 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 remainders, maybe is not a good idea, I'm not sure. Any proposal or comment? 


  [1]: https://i.sstatic.net/UEJZ0.png