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  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 the count of its complement, and accumulating the one with the maximum value. The following picture explains the idea, for the following reminders 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 reminder 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 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;
        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 reminders, maybe is not a good idea, I'm not sure. Any proposal or comment? 


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