#781
Medium Algorithms Rabbits in forest
Array Hash Table Math Greedy
58.1% acceptance
Feb 21, 2026
2136
988
There is a forest with an unknown number of rabbits. We asked n rabbits "How many other 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.
Solution
Rust
Time O(n)
Space O(n)
/*
* 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
*/
use std::collections::HashMap;
impl Solution {
pub fn num_rabbits(answers: Vec<i32>) -> i32 {
let mut freq: HashMap<i32, i32> = HashMap::new();
for a in answers { *freq.entry(a).or_insert(0) += 1; }
freq.iter().map(|(&a, &count)| {
let grp = a + 1;
((count + grp - 1) / grp) * grp
}).sum()
}
}