#781

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Rabbits in Forest

Solve Rabbits in Forest by grouping equal answers and rounding each group into the smallest valid color-class size.

Problem Statement

You are given an array where each value is a rabbit's reply to the question: how many other rabbits share your color? The forest size is unknown, and some rabbits of the same color may not appear in the array because only certain rabbits were asked.

Your task is to return the minimum total number of rabbits that could exist while keeping every reported value consistent. In Rabbits in Forest, the key constraint is that an answer x represents a color class of exactly x + 1 rabbits, so repeated answers must be grouped carefully instead of counted one by one.

Examples

Example 1

Input: answers = [1,1,2]

Output: 5

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

Example details omitted.

Constraints

1 <= answers.length <= 1000
0 <= answers[i] < 1000

Solution Approach

Count how many times each answer appears

Scan the array once and store frequencies in a hash map. For Rabbits in Forest, this turns the raw replies into buckets where each distinct answer x has count c, which is the only information needed to compute the minimum forest size.

Convert each answer into fixed-size color groups

If a rabbit says x, then its color group must contain x + 1 rabbits total. For a frequency c of that answer, the number of required groups is ceil(c / (x + 1)). Each such group contributes x + 1 rabbits, including any unseen rabbits needed to complete the final partial group.

Sum the contribution from every bucket

Add ceil(c / (x + 1)) * (x + 1) over all distinct answers. For example, with answers = [1,1,2], the two 1s fit into one group of size 2, while the single 2 forces one full group of size 3, so the minimum total is 2 + 3 = 5.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Using array scanning plus hash lookup, the standard solution runs in O(n) time because each rabbit is counted once and each distinct answer is processed once. It uses O(n) space in the worst case for the frequency map, although the actual space is O(u) where u is the number of unique answers. The important trade-off in this problem is simplicity versus overthinking: once frequencies are known, the math is just rounded group packing.

What Interviewers Usually Probe

The interviewer expects you to notice that an answer x defines a group size of x + 1, not just x matching rabbits.
They want a greedy counting argument showing why partially filled groups still force the full group cost.
They are checking whether you reach for a hash map quickly instead of trying to simulate rabbit colors explicitly.

Common Pitfalls or Variants

Common pitfalls

Adding the frequency count directly and forgetting the hidden rabbits needed to complete a color group.
Treating every repeated answer as one shared group even when the count exceeds x + 1 and must spill into another group.
Mixing up x with x + 1, which breaks both the grouping formula and the example [1,1,2].

Follow-up variants

Ask for the maximum possible rabbits instead of the minimum, which removes the tight greedy packing used in Rabbits in Forest.
Stream the answers one by one and maintain the same grouped counting logic online with incremental frequencies.
Return the number of color groups as well as the minimum rabbit count, using the same ceil(c / (x + 1)) computation per answer.

FAQ

What is the core trick in Rabbits in Forest?

The core trick is that each reply x represents a full color class of size x + 1. After counting how many times x appears, you round that count up into groups of size x + 1 instead of adding the replies directly.

Why does answers = [1,1,2] produce 5?

The two rabbits who said 1 can be one color group of size 2. The rabbit who said 2 must belong to a separate color group of size 3, which means two additional unseen rabbits are required, giving 2 + 3 = 5.

Why use a hash map for this pattern?

The array scanning plus hash lookup pattern works because only the frequency of each answer matters. Once you know how many times each x appears, the minimum contribution for that bucket is determined by the group-size formula.

Can I sort instead of using a hash table?

Yes, sorting also lets you process equal answers together, but it changes the time cost to O(n log n). The hash-map version is usually preferred in interviews because Rabbits in Forest only needs frequencies, not order.

What happens when a rabbit answers 0?

An answer of 0 means that rabbit's color group has size 1, so it contributes exactly one rabbit. Multiple zeros do not merge, because each zero describes a rabbit with no same-color partners.

terminal

Solution

Solution 1: Greedy + Hash Map

According to the problem description, rabbits that give the same answer may belong to the same color, while rabbits that give different answers cannot belong to the same color.

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        cnt = Counter(answers)
        ans = 0
        for x, v in cnt.items():
            group = x + 1
            ans += (v + group - 1) // group * group
        return ans

Solution 2: Greedy + Hash Map

#### TypeScript

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        cnt = Counter(answers)
        ans = 0
        for x, v in cnt.items():
            group = x + 1
            ans += (v + group - 1) // group * group
        return ans

Continue Practicing

#840 magic squares in grid #846 hand of straights #710 random pick with blacklist