Rabbits in Forest

Medium
1780.

Rabbits in Forest

Rabbits in Forest is a medium coding problem on arrays, hash table and math, asked in Amazon and Google interviews.

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 <= 1000
  • 0 <= answers[i] < 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} answers
 * @return {number}
 */
var numRabbits = function(answers) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 1000
  • 0 <= answers[i] < 1000

Hints for Rabbits in Forest

  1. Hint 1

    A rabbit that answers x belongs to a colour group of exactly x + 1 rabbits.

  2. Hint 2

    Rabbits giving the same answer can share a group — but only x + 1 of them can.

  3. Hint 3

    If c rabbits answered x, they need ceil(c / (x + 1)) groups of x + 1 rabbits 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

  1. Count how many rabbits gave each answer.
  2. For each answer x with count c, add ceil(c / (x + 1)) * (x + 1).
  3. 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 + 1 once per distinct answer undercounts when more than x + 1 rabbits 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 total

Java

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