Skip to content

781. Rabbits in Forest

Description

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

Solutions

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.

Therefore, we use a hash map \(\textit{cnt}\) to record the number of occurrences of each answer. For each answer \(x\) and its occurrence \(v\), we calculate the minimum number of rabbits based on the principle that each color has \(x + 1\) rabbits, and add it to the answer.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Where \(n\) is the length of the array \(\textit{answers}\).

1
2
3
4
5
6
7
8
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int numRabbits(int[] answers) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : answers) {
            cnt.merge(x, 1, Integer::sum);
        }
        int ans = 0;
        for (var e : cnt.entrySet()) {
            int group = e.getKey() + 1;
            ans += (e.getValue() + group - 1) / group * group;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func numRabbits(answers []int) (ans int) {
    cnt := map[int]int{}
    for _, x := range answers {
        cnt[x]++
    }
    for x, v := range cnt {
        group := x + 1
        ans += (v + group - 1) / group * group
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function numRabbits(answers: number[]): number {
    const cnt = new Map<number, number>();
    for (const x of answers) {
        cnt.set(x, (cnt.get(x) || 0) + 1);
    }
    let ans = 0;
    for (const [x, v] of cnt.entries()) {
        const group = x + 1;
        ans += Math.floor((v + group - 1) / group) * group;
    }
    return ans;
}

Comments