HackerRank - Non-Divisible Subset

Question

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

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?

Answer 1

I'm not sure about what makes your code slow, but first I should point out some ways to improve its readability. Actually, it should help you to think about your code complexity to make it more readable, since performance in complex nested loops and such things is really difficult to evaluate.

To begin with a detail, I believe that:

std::for_each(v.begin(), v.end(), [&k](auto& x){x%=k;});

isn't the most readable. When you iterate over the whole container, the "range-based" for is better:

for (auto& x : v) x %= k;

unless you want to make your intent yet more apparent with the transform algorithm:

std::transform(vec.begin(), vec.end(), vec.begin(), [k](auto&& i) {return i%k;});

More importantly, I think you should dissociate traversal and counting, because it makes for a code very difficult to read. Why don't you make it in two steps:

// first step: counting modulo populations
std::map<int, int> counter;
for (auto elem: v) ++counter[v%k];

// second step: traversing different modulos
auto no_duplicates = std::unique(vec.begin(), vec.end());
std::for_each(vec.begin, no_duplicates, [](auto etc) { do_something(etc); });

A last point, you can put the two special cases out of the way early, instead of dragging them along until the end. So deal with multiples of k and k/2 at the first occasion, it also allows you to get rid of a certain number of elements.

To sum it up, here's my suggestion:

int nonDivisibleSubset(int k, std::vector<int> vec) {
    // 1. check for multiples of k, multiples of half of k, and retain only one of each
    int res = 0;
    auto multiples = std::remove_if(vec.begin(), vec.end(), [k](auto&& i) { return i%k == 0; }); 
    if (multiples != vec.end()) ++res;
    auto half_multiples = std::remove_if(vec.begin(), multiples, [k](auto&& i) { return 2*(i%k) == k; });
    if (half_multiples != multiples) ++res;
    // 2. for each possible modulo-complementary couple, choose the one with the most occurrences
    std::transform(vec.begin(), half_multiples, vec.begin(), [k](auto&& i) {return i%k;}); // calculate modulos
    std::sort(vec.begin(), half_multiples);
    std::map<int, int> mods; // count their occurrences
    std::for_each(vec.begin(), half_multiples, [&mods](auto&& i) {++mods[i];});
    // and then examine each possible couple
    auto uniques = std::unique(vec.begin(), half_multiples); 
    auto bottom_up = vec.begin();
    auto top_down = std::reverse_iterator<std::vector<int>::iterator>(uniques);
    while (bottom_up < top_down.base()) {
        if (*bottom_up + *top_down == k) { // complementary
            res += std::max(mods[*bottom_up], mods[*top_down]);
            ++bottom_up, ++top_down;
        }
        // if not complementary advance the closest from its origin
        else if (*bottom_up < k - *top_down ) { 
            res += mods[*bottom_up++];
        }
        else res += mods[*top_down++];
    }
    return res;
}

P.S: I've tried to submit that code and it passes correctly.

Answer 2

I've finally made it work

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

int non_divisible_subset_size(int k, std::vector<int> &v) {
    // Count the mods occurrencies
    using value = int; using occurencies = int;
    std::map<value, occurencies> mods;
    std::for_each(v.begin(), v.end(), [&mods,k](auto& x) {++mods[x%k];});
    // 0 and k/2 mods can only be included once
    int subset_size{0};
    auto zero_mod = mods.find(0);
    if (zero_mod != mods.end()) {
        ++subset_size;
        mods.erase(zero_mod);
    }
    if (k%2 == 0) {
        auto half_k_mod = mods.find(k/2);
        if (half_k_mod != mods.end()) {
            ++subset_size;
            mods.erase(half_k_mod);
        }
    }
    if (mods.begin() == mods.end()) return subset_size;
    // For each mod x there is only other mod x-k
    // (with x-k > k/2) that sums up to k. 
    // For each pair count the one with more ocurrencies.
    if (mods.size()==1) return subset_size += mods.begin()->second;
    auto bottom_up = mods.begin();
    auto top_down = mods.rbegin();
    while (bottom_up->first <= top_down->first) {
        if (bottom_up->first + top_down->first == k) {
            subset_size += std::max(bottom_up->second,top_down->second);
            ++bottom_up, ++top_down;
        }
        // if not complementary count and advance the outter one
        else {
            if (top_down->first < k - bottom_up->first) {
                subset_size += mods[bottom_up->first];
                ++bottom_up;
            }
            else {
                subset_size += mods[top_down->first];
                ++top_down;
            }
        }
    }
    return subset_size;
}

int main() {
    int n;
    int k;
    std::cin >> n >> k;
    std::vector<int> v(n);
    for(int i = 0; i < n; ++i){
       std::cin >> v[i];
    }

    int result = non_divisible_subset_size(k, v);
    std::cout << result << std::endl;
}

The trick was the way to look for the pairs, the bottom_up top_down approach of papagaga was faster than finding the elements.