# Rabbits in Forest
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/rabbits-in-forest)
Canonical: https://scaleengineer.com/dsa/problems/rabbits-in-forest
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Hash Table
**Companies:** [Zepto](https://scaleengineer.com/companies/zepto), [CARS24](https://scaleengineer.com/companies/cars24), [Cleartrip](https://scaleengineer.com/companies/cleartrip), [Wish](https://scaleengineer.com/companies/wish)
---
## Problem
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 <= 1000`
* `0 <= answers[i] < 1000`

# Approaches
## Sorting and Grouping
This approach first sorts the input array `answers`. By sorting, all rabbits who gave the same answer are grouped together. We can then iterate through the sorted array, processing each group of identical answers to calculate the number of rabbits required for that group.
**Time:** O(N log N), where N is the number of elements in `answers`. The dominant operation is sorting the array. The subsequent scan of the array takes O(N) time. · **Space:** O(log N) or O(N), depending on the implementation of the sorting algorithm. In Java, `Arrays.sort` for primitives uses a variant of Quicksort which has an average space complexity of O(log N).
**Pros:** The approach is relatively simple to conceptualize.; It does not require any auxiliary data structures like a HashMap, modifying the input array in-place (if allowed) or using the space provided by the sorting algorithm.
**Cons:** The sorting step has a time complexity of O(N log N), which is less efficient than linear time solutions.
### Explanation
The fundamental logic is that if a rabbit answers `x`, it belongs to a color group of size `x + 1`. All rabbits that give the same answer `x` can potentially belong to the same color group. By sorting the `answers` array, we place all identical answers adjacent to each other, making them easy to process as a single block. We iterate through the sorted array, and for each block of identical answers `x` of size `k`, we calculate how many groups of size `x + 1` are needed. Since each group can contain at most `x + 1` such rabbits, we need `ceil(k / (x + 1))` groups. The total number of rabbits for this color is then `ceil(k / (x + 1)) * (x + 1)`. We sum this value for each distinct answer to find the overall minimum number of rabbits.

```java
import java.util.Arrays;

class Solution {
    public int numRabbits(int[] answers) {
        if (answers == null || answers.length == 0) {
            return 0;
        }
        Arrays.sort(answers);
        int totalRabbits = 0;
        int i = 0;
        while (i < answers.length) {
            int currentAnswer = answers[i];
            int groupSize = currentAnswer + 1;
            int count = 0;
            int j = i;
            while (j < answers.length && answers[j] == currentAnswer) {
                count++;
                j++;
            }
            // Using ceiling division: (numerator + denominator - 1) / denominator
            int numGroups = (count + groupSize - 1) / groupSize;
            totalRabbits += numGroups * groupSize;
            i = j;
        }
        return totalRabbits;
    }
}
```
### Algorithm
1. Sort the `answers` array in non-decreasing order.
2. Initialize `totalRabbits = 0` and an index `i = 0`.
3. Loop while `i` is less than the length of the array:
    a. Get the current answer `x = answers[i]`.
    b. The size of a color group for this answer is `groupSize = x + 1`.
    c. Count the number of rabbits `k` that gave the same answer `x`. This can be done by finding the next index `j` where `answers[j] != x`. The count `k` will be `j - i`.
    d. Calculate the number of groups needed using ceiling division: `numGroups = (k + groupSize - 1) / groupSize`.
    e. Add the total rabbits for this color to the result: `totalRabbits += numGroups * groupSize`.
    f. Move the index `i` to `j` to start processing the next distinct answer.
4. Return `totalRabbits`.

## Frequency Counting with a HashMap
A more efficient approach is to count the frequency of each answer without sorting. A HashMap is a perfect data structure for this task. We can iterate through the `answers` array once to populate the HashMap with counts, and then iterate through the HashMap's entries to calculate the total number of rabbits based on these frequencies.
**Time:** O(N), where N is the length of the `answers` array. This is because we iterate through the array once to build the map and then iterate through the unique answers (at most N). · **Space:** O(U), where U is the number of unique answers. In the worst-case scenario where all N answers are distinct, the space complexity is O(N).
**Pros:** Achieves optimal O(N) time complexity.; It is flexible and works for any range of integer values in the `answers` array, not just small, bounded ones.
**Cons:** Uses extra space for the HashMap, which can be up to O(N) in the worst case where all answers are unique.; May have a slight performance overhead due to hash calculations and potential collisions compared to a direct-access array.
### Explanation
This approach avoids the O(N log N) sorting step by using a hash map to count frequencies in linear time. We first populate a map where keys are the answers given by rabbits and values are the number of rabbits that gave that answer. After counting, we iterate through the map. For each answer `x` with a count of `k`, we apply the same logic as before: these `k` rabbits belong to groups of size `x + 1`. We calculate the minimum number of groups required, which is `ceil(k / (x + 1))`, and multiply it by the group size `x + 1` to find the total rabbits for that color. Summing these results across all unique answers gives the final minimum total.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int numRabbits(int[] answers) {
        if (answers == null || answers.length == 0) {
            return 0;
        }
        Map<Integer, Integer> counts = new HashMap<>();
        for (int answer : answers) {
            counts.put(answer, counts.getOrDefault(answer, 0) + 1);
        }

        int totalRabbits = 0;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            int answer = entry.getKey();
            int count = entry.getValue();
            int groupSize = answer + 1;
            int numGroups = (count + groupSize - 1) / groupSize;
            totalRabbits += numGroups * groupSize;
        }
        return totalRabbits;
    }
}
```
### Algorithm
1. Create a `HashMap<Integer, Integer>` called `counts` to store the frequency of each answer.
2. Iterate through the `answers` array. For each `answer`, update its frequency in the `counts` map.
3. Initialize `totalRabbits = 0`.
4. Iterate through each entry `(answer, count)` in the `counts` map:
    a. The size of a color group is `groupSize = answer + 1`.
    b. Calculate the number of groups needed for this answer: `numGroups = (count + groupSize - 1) / groupSize`.
    c. Add the total rabbits for this color to the result: `totalRabbits += numGroups * groupSize`.
5. Return `totalRabbits`.

## Frequency Counting with an Array
Given the problem's constraints that answers are non-negative and less than 1000, we can optimize the frequency counting by using a fixed-size array instead of a HashMap. This approach leverages direct array indexing, which is generally faster than hashing, making it the most performant solution for the given constraints.
**Time:** O(N + M), where N is the length of `answers` and M is the range of possible answer values. Given M=1000, this is effectively O(N) as N can be up to 1000. · **Space:** O(M), where M is the maximum possible value for an answer plus one. Given the constraints, this is O(1000), which is constant space.
**Pros:** Extremely fast due to direct array access, avoiding hashing overhead.; Maintains an optimal linear time complexity.; Simple to implement.
**Cons:** The space complexity is dependent on the maximum possible value of an answer, not the number of answers or unique answers. If the range of answers were very large, this approach would be infeasible.; It is less flexible than the HashMap approach if the constraints on the answer values change.
### Explanation
This method is a specialized version of the HashMap approach, tailored to the specific constraints of the problem. Since `answers[i]` is between 0 and 999, we can use an array of size 1001 as a direct address table or frequency map. `counts[i]` will store the number of rabbits that answered `i`. We first pass through the `answers` array to populate our `counts` array. Then, we iterate through the `counts` array from index 0 to 1000. For each index `i` where `counts[i]` is greater than zero, we perform the same calculation as in the previous approaches to find the total number of rabbits for that color group and add it to our running total. This avoids the overhead of HashMap's hashing and object creation, leading to better performance.

```java
class Solution {
    public int numRabbits(int[] answers) {
        if (answers == null || answers.length == 0) {
            return 0;
        }
        // answers[i] is in the range [0, 999]
        int[] counts = new int[1000];
        for (int answer : answers) {
            counts[answer]++;
        }

        int totalRabbits = 0;
        // A rabbit answering 0 is in a group of 1 (itself)
        totalRabbits += counts[0];

        for (int i = 1; i < 1000; i++) {
            if (counts[i] == 0) {
                continue;
            }
            int count = counts[i];
            int answer = i;
            int groupSize = answer + 1;
            int numGroups = (count + groupSize - 1) / groupSize;
            totalRabbits += numGroups * groupSize;
        }
        return totalRabbits;
    }
}
```
### Algorithm
1. Create an integer array `counts` of size 1001 (since `0 <= answers[i] < 1000`) and initialize it with zeros.
2. Iterate through the `answers` array. For each `answer`, increment `counts[answer]`.
3. Initialize `totalRabbits = 0`.
4. Iterate from `i = 0` to `1000` (the range of possible answers):
    a. If `counts[i] == 0`, continue to the next iteration.
    b. Let `answer = i` and `count = counts[i]`.
    c. The size of a color group is `groupSize = answer + 1`.
    d. Calculate the number of groups needed: `numGroups = (count + groupSize - 1) / groupSize`.
    e. Add the total rabbits for this color to the result: `totalRabbits += numGroups * groupSize`.
5. Return `totalRabbits`.

# Solutions
### Java

```java
class Solution {
public
  int numRabbits(int[] answers) {
    Map<Integer, Integer> counter = new HashMap<>();
    for (int e : answers) {
      counter.put(e, counter.getOrDefault(e, 0) + 1);
    }
    int res = 0;
    for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
      int answer = entry.getKey(), count = entry.getValue();
      res += (int)Math.ceil(count / ((answer + 1) * 1.0)) * (answer + 1);
    }
    return res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numRabbits(vector<int> &answers) {
    unordered_map<int, int> cnt;
    for (int x : answers) {
      ++cnt[x];
    }
    int ans = 0;
    for (auto &[x, v] : cnt) {
      int group = x + 1;
      ans += (v + group - 1) / group * group;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numRabbits(self, answers: List[int]) -> int: counter = Counter(answers) return sum([math . ceil(v / (k + 1)) * (k + 1) for k, v in counter . items()])

```