Rabbits in Forest

Leetcode Problem:

• Rabbits in Forest

Summary

• Find the minimum number of rabbits in the forest given the answers to the question about the number of rabbits of the same color.

Approach

• The solution uses an array to count the frequency of each color of rabbit
• It then iterates over the array, adding the number of rabbits of each color to the total answer
• If a color has no rabbits, it is skipped
• The solution assumes that the number of rabbits of a color is a multiple of the number of rabbits that answered the question.

Complexity

• O(n), where n is the number of rabbits that answered the question, because each rabbit is counted once.

Solution Code:

class Solution {
public:
    int sameCnt[1001];
    int numRabbits(vector& answers) {
        for(int i = 0 ; i < answers.size(); i++){
            sameCnt[answers[i]]++;
        }
        int ans = sameCnt[0];
        for(int i = 1 ; i < 1000; i++){
            if(sameCnt[i] == 0) continue;
            ans += (i+1)*((sameCnt[i] - 1)/ (i + 1) + 1);
        }
        return ans;
    }
};