selling_products.md

// 80 ms in worst case
int solve(vector<int>& a, int n) {
    if (a.size() == 0) return 0;
    sort(a.begin(), a.end());
    int w = 0;
    int c = 1;
    int x = a[0];
    int y;
    for (int i = 1; i < a.size(); i++) {
        y = a[i];
        if (y == x) {
            c++;
        } else {
            x = y;
            a[w++] = c;
            c = 1;
        }
    }
    a[w++] = c;

    // a.erase(a.begin()+w, a.end()); // but we don't really care
    sort(a.begin(), a.begin() + w);

    for (int i = 0; i < w; i++) {
        n -= a[i];
        if (n < 0) return w - i;
    }
    return 0;
}

# 50 ms in worst case
def solve(items, n)
    items.tally.map{|_,x|x}.sort.drop_while{|x|(n-=x)>=0}.size
end