Rabbits in Forest
Problem
Each rabbit reports how many other rabbits share its color. Compute the minimum number of rabbits possible in the forest.
answers=[1,1,2]5from collections import Counter
def numRabbits(answers):
cnt = Counter(answers)
ans = 0
for x, c in cnt.items():
group = x + 1
ans += ((c + group - 1) // group) * group
return ansfunction numRabbits(answers) {
const cnt = new Map();
for (const a of answers) cnt.set(a, (cnt.get(a) || 0) + 1);
let ans = 0;
for (const [x, c] of cnt) {
const group = x + 1;
ans += Math.ceil(c / group) * group;
}
return ans;
}int numRabbits(int[] answers) {
Map<Integer,Integer> cnt = new HashMap<>();
for (int a : answers) cnt.merge(a, 1, Integer::sum);
int ans = 0;
for (var e : cnt.entrySet()) {
int x = e.getKey(), c = e.getValue(), group = x + 1;
ans += ((c + group - 1) / group) * group;
}
return ans;
}int numRabbits(vector<int>& answers) {
unordered_map<int,int> cnt;
for (int a : answers) cnt[a]++;
int ans = 0;
for (auto& [x, c] : cnt) {
int group = x + 1;
ans += ((c + group - 1) / group) * group;
}
return ans;
}Explanation
The key insight is that rabbits giving the same answer can be grouped together. If a rabbit says x others share its color, its whole color-group has exactly x + 1 rabbits. So every rabbit that answered x belongs in a group of that size.
We first count how many rabbits gave each answer using a Counter. If c rabbits all answered x, they may not all fit in one group of size x + 1, so we need enough full groups to hold them: ceil(c / (x+1)) groups.
Each group always counts as a full x + 1 rabbits even if it is not completely filled, because a color-group of that size must really exist. So the contribution for answer x is ceil(c / (x+1)) * (x+1), and we add that up over all answers.
The expression (c + group - 1) // group is just an integer way to compute ceil(c / group) without floating point.
Example: answers = [1,1,2]. The two 1's: group size 2, ceil(2/2)=1 group = 2 rabbits. The single 2: group size 3, ceil(1/3)=1 group = 3 rabbits. Total = 2 + 3 = 5.