Rabbits in Forest — Solution in Python, Java & C++
Rabbits in Forest solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Rabbits in Forest is a medium coding problem on arrays, hash table and math, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Math, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A forest holds an unknown number of rabbits, each of one colour. You ask some of them the question "How many other rabbits share your colour?" and record the replies in answers, where answers[i] is the reply of the i-th rabbit you asked. Every rabbit answers truthfully.
Return the minimum number of rabbits that could be living in the forest.
Example 1
Input: answers = [1,1,2]
Output: 5
Explanation: The two rabbits that said 1 can share one colour (a group of 2). The rabbit that said 2 belongs to a group of 3, of which we met only one, so two more exist. 2 + 3 = 5.
Example 2
Input: answers = [10,10,10]
Output: 11
Explanation: All three can belong to the same group of 11 rabbits.
Example 3
Input: answers = [0,0,1,1,1]
Output: 6
Explanation: Each 0 is a rabbit alone in its colour (2 rabbits). Three rabbits said 1, but a group of that colour holds only 2, so they need two groups: 4 rabbits.
Constraints
1 <= answers.length <= 10000 <= answers[i] < 1000
Hints for Rabbits in Forest
Hint 1
A rabbit that answers
xbelongs to a colour group of exactlyx + 1rabbits.Hint 2
Rabbits giving the same answer can share a group — but only
x + 1of them can.Hint 3
If
crabbits answeredx, they needceil(c / (x + 1))groups ofx + 1rabbits each.
How to solve Rabbits in Forest
An answer x pins its rabbit to a group of size x + 1. To minimise the total, pack rabbits with the same answer into as few such groups as possible.
Approach
- Count how many rabbits gave each answer.
- For each answer
xwith countc, addceil(c / (x + 1)) * (x + 1). - Return the sum.
Why it works
Rabbits with different answers can never share a colour (they would disagree about the group size), so answers are independent. Within one answer x, each group holds at most x + 1 of the rabbits we met, so at least ceil(c / (x + 1)) groups exist, each contributing exactly x + 1 rabbits; filling groups greedily achieves that bound.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Counting
x + 1once per distinct answer undercounts when more thanx + 1rabbits gave the same answer. - An answer of 0 is a group of one, so every such rabbit counts separately.
Reference solution
Python
from typing import List
from collections import Counter
def numRabbits(answers: List[int]) -> int:
total = 0
for x, c in Counter(answers).items():
size = x + 1
total += (c + size - 1) // size * size
return totalJava
public static int numRabbits(int[] answers) {
int[] cnt = new int[1001];
for (int a : answers) cnt[a]++;
int total = 0;
for (int x = 0; x <= 1000; x++) {
if (cnt[x] == 0) continue;
int size = x + 1;
total += (cnt[x] + size - 1) / size * size;
}
return total;
}C++
int numRabbits(vector<int>& answers) {
vector<int> cnt(1001, 0);
for (int a : answers) cnt[a]++;
int total = 0;
for (int x = 0; x <= 1000; x++) {
if (cnt[x] == 0) continue;
int size = x + 1;
total += (cnt[x] + size - 1) / size * size;
}
return total;
}JavaScript
var numRabbits = function(answers) {
var cnt = new Array(1001).fill(0);
for (var i = 0; i < answers.length; i++) cnt[answers[i]]++;
var total = 0;
for (var x = 0; x <= 1000; x++) {
if (cnt[x] === 0) continue;
var size = x + 1;
total += Math.floor((cnt[x] + size - 1) / size) * size;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets