Leetcode 781: Rabbits in Forest

https://leetcode.com/problems/rabbits-in-forest/description/

Notes:

This question is another brain teaser.

For these kinds of questions, one way seems always starting with some small-size samples.

Let us consider [0, 0]. It means that there are at least 2 kinds of colors. So we can make a conclusion to value of 0: every 0 represents one of kind of color.

Now [1, 1]. It can be 2 rabbits with the same color. How about [1, 1, 1]? The first two can be one color, but the last 1 cannot be the same color. If the same, then first rabbit should answer 2 instead of 1 (the same as the second and the third). So there are at least 4 rabbits: with 2 of them having the same color.

How about [1, 1, 1, 1]? Based on the above analysis, it is easy to figure it out: there are at least 4 rabbits. One solution is: the first two share one color, and the rest two share another color.

How about [1, 1, 1, 1, 1]? The answer is 6.

How about [1, 1, 1, 1, 1, 1]? The answer still is 6.

Now we can make some summaries:

if the counting of val is no larger than (val + 1), then all the rabbits can share one kind of color. If there are more, we need to use another color. Or, another way to say this is that: one color can only be assigned to (val + 1) rabbits. For example, [3, 3, 3, 3] can be at least 4 rabbits. Here val == 3.

So now we just to count the apparent times of each val, then compare them with (val + 1).

See the code below:

class Solution {
public:
    int numRabbits(vector<int>& answers) {
        int res = 0;
        vector<int> ct(1001, 0);
        for(auto &a : answers) ++ct[a];
        for(int i = 0; i<ct.size(); ++i) {//i = 0 can also be calculated in the same way
            if(ct[i] > 0) {//this for loop can be re-written in one line...
                int a = ct[i]/(i+1), b = ct[i]%(i+1);
                res += a*(i+1);
                if(b>0) res += i+1;
            }
        }
        return res;
    }
};