There is a forest with an unknown number of rabbits. We asked n rabbits "How many rabbits have the same color as you?" and collected the answers in an integer array answers where answers[i] is the answer of the ith rabbit.
Given the array answers, return the minimum number of rabbits that could be in the forest.
Example 1:
Input: answers = [1,1,2] Output: 5 Explanation: The two rabbits that answered "1" could both be the same color, say red. The rabbit that answered "2" can't be red or the answers would be inconsistent. Say the rabbit that answered "2" was blue. Then there should be 2 other blue rabbits in the forest that didn't answer into the array. The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.
Example 2:
Input: answers = [10,10,10] Output: 11
Constraints:
1 <= answers.length <= 10000 <= answers[i] < 1000The key idea in #781 Rabbits in Forest is understanding how rabbits report the number of other rabbits with the same color. If a rabbit says x, it means there are x other rabbits with the same color, forming a group of size x + 1. Multiple rabbits may give the same answer, but they must be grouped carefully so that each group does not exceed its allowed size.
A practical strategy is to use a hash table to count how many times each answer appears. For each value x, determine how many complete groups of size x + 1 are required to accommodate all rabbits that reported x. If the count exceeds one group, additional groups must be formed. This greedy grouping ensures the minimum possible number of rabbits in the forest.
This approach efficiently processes the array in a single pass with counting logic. The method relies on greedy reasoning and frequency tracking, resulting in linear time complexity and minimal additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Table + Greedy Grouping | O(n) | O(n) |
Pepcoding
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Rabbits in Forest is a common interview-style problem that tests greedy reasoning, counting logic, and hash table usage. Variations of this problem can appear in interviews at top tech companies.
A hash map (or dictionary) is the most effective data structure. It helps track the frequency of each reported value and allows efficient calculation of how many groups of rabbits must exist.
The optimal approach uses a hash table to count how many rabbits report the same number. Each answer x implies groups of size x + 1, and greedy grouping ensures the minimum number of rabbits. This method runs in linear time.
If a rabbit reports x, it means there are x other rabbits with the same color. Therefore, the total number of rabbits sharing that color must be x + 1, which defines the maximum size of that group.