Return to Question

###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.

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.

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.

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 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.

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;
}

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?

###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.

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;
}

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?