Description

You are given N balls and an integer K.The color of each ball is given in an array.A basket is filled if it contains at least K balls of different colors. Find the maximum number of filled baskets you can get if you optimally put the balls in the baskets.

How to approach the problem , as we know that number of buckets function will be increasing function , reason is if we are able to find x buckets , then we can easily find all below x , so we think on only greater than x buckets , simillarly if we are unable to find x buckets , then we can't find > x buckets as well , so we move left..

So , we start with left = 0, right = N / K , we find whether it is possible for mid buckets ..

How to check above ??

map<int,int>freq;
int balls = 0;
for(auto it : freq){
    balls += min(mid,it.second);
}
if(balls >= (k * mid)){
    ans = mid;
    left = mid + 1;
}else{
    right = mid - 1;
}

As we know that for each colour we at most use mid times , if we take mid buckets , so we take min(mid,it.second) , if we take more than mid colors , then it may be compensate others lead to non distnct colors in a single bucket..