Rabbits in Forest

Today, let’s go to the forest and conduct a survey. This would be an interesting task. We specifically choose rabbits and when we meet one, we ask him, hey How many rabbits of your color have you seen in this forest? In a hypothetical world where you know how to communicate with a rabbit, it would be an amazing activity. Now, let’s get into the problem first.

Problem Statement

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 $i^{th}$ rabbit.

Given the array $answers$, return the minimum number of rabbits that could be in the forest. [1]

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

Greedy Algorithm

We solve this problem using a Greedy Algorithm and a Hash Table. When we encounter a Rabbit, we ask him a question and record the answer. The answers are given in the input sequence. We iterate over the input sequence and add the answer into a Hash Table. In our Hash Table, we maintain a mapping from a given answer to the number of Rabbits responded with that answer. Now, we have the Hash Table with the data we need.

Then, we consider each key and value pair in the Hash Table. Let $k$ and $v$ be the key-value pair respectively. That implies, $v$ number of rabbits voted for $k$ other rabbits to have the same color as itself. Thus, the group size would be exactly $k + 1$. Now, we assign these rabbits to a minimum number of groups as possible as that minimizes the overall number of rabbits in the forest. This is our greedy choice property.

What follows is the greedy algorithm we designed to solve this problem.

NUM_RABBITS(answers)  

    $\phantom{{}++{}}$ let $t$ be a hash table  

    $\phantom{{}++{}}$ `foreach` $response \in answers$  

    $\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $response \in t$  

    $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ then increment the associated value by one  

    $\phantom{{}++{}}$ $\phantom{{}++{}}$`else`  

    $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ insert the $answer$ as the key and one as the value in the $t$      

    $\phantom{{}++{}}$ let $ans = 0$  

    $\phantom{{}++{}}$ `foreach` key-value pair $\{k, v\}\in t$  

    $\phantom{{}++{}}$ $\phantom{{}++{}}$ let $r \gets v \mod \ (k + 1)$    

    $\phantom{{}++{}}$ $\phantom{{}++{}}$  `if` $r = 0$  

    $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $ans \gets ans + v$  

    $\phantom{{}++{}}$ $\phantom{{}++{}}$ `else`  

    $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $ans \gets ans + v + k + 1 - r$  

    $\phantom{{}++{}}$ `return` $ans$  

Sample Implementation

Here’s our sample implementation of the Greedy solution.

	class RabbitsInForest {
	RabbitsInForest() {
	throw new AssertionError();
	}
	public static void main(String[] args) {
	final int[] ans1 = { 1, 1, 2 };
	assert numRabbits(ans1) == 5;
	final int[] ans2 = { 10, 10, 10 };
	assert numRabbits(ans2) == 11;
	}
	static int numRabbits(int[] answers) {
	final Map<Integer, Integer> t = new HashMap<>();
	for (int response : answers)
	t.merge(response, 1, Integer::sum);
	int ans = 0;
	for (Entry<Integer, Integer> e : t.entrySet()) {
	final int k = e.getKey();
	ans = ans + (e.getValue() + k) / (k + 1) * (k + 1);
	}
	return ans;
	}
	}

view raw RabbitsInForest.java hosted with ❤ by GitHub

Proof of correctness

Let $t$ be our hash table and $k$, $v$ be our key and value pair respectively.

Lemma 1.0

For a given key value pair $k$ and $v$, minimizing the number of groups $v$ number of rabbits belongs to, minimizes the total number of rabbits in the forest.

Proof

There are many satisfiable assignments of rabbits into different color groups. However, only some of them yield the optimal solution. Let $k$ and $v$ be the key value pair we currently consider. Let us assume that our above designed algorithm assigns $v$ rabbits into $g'$ number of groups whereas some other satisfiable assignments of rabbits into colored groups yields $g''$ different groups such that $g'' \gt g'$. Other than that, let’s assume that both of these assignments gives the same result $a$, for all the key value pairs except for the one being considered here which is $k$ and $v$ respectively. Moreover, let’s assume that this later assignment gives us the minimum number of total rabbits in the forest, which is the optimal solution. Now let $a'$ and $a''$ be the answers given by our assignment and the other optimal assignment respectively.

$a' = a\  +\ g' \times (k+1)$  

$a'' = a\  +\ g'' \times (k+1)$  

we know that $g'' \gt g'$  

Thus, $a'' \gt a'$  

A contradiction. Thus, proving our claim.

Theorem 1.0

The procedure $NUM\_RABBITS$ produces an assignment of rabbits into different color groups such that it gives the minimum number of rabbits in the forest. 

Proof

Immediately follows from Lemma 1.0.

Analysis

Our Greedy algorithm involves $\Theta(n)$ asymptotic time and $\Theta(n)$ asymptotic space complexity.

References

[1] https://leetcode.com/problems/rabbits-in-forest/description