781. Rabbits in Forest

LeetCode 781. Rabbits in Forest

Description

In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those answers are placed in an array.

Return the minimum number of rabbits that could be in the forest.

Examples:
Input: answers = [1, 1, 2]
Output: 5
Explanation:
The two rabbits that answered "1" could both be the same color, say red.
The rabbit than 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.

Input: answers = [10, 10, 10]
Output: 11

Input: answers = []
Output: 0

Note:

1. answers will have length at most 1000.

2. Each answers[i] will be an integer in the range [0, 999].

Tags

Hash Table, Math

Solution

相同颜色的兔子看见其他同色兔子的数目一定相同，反之，若两只兔子看见与自身同色兔子数目不同则这两只一定不是同色。因此，我们使用哈希表，把报数相同的兔子划分为同一组，并将每一组可计算出的最少兔子数目累加到结果上。

例如有13只兔子回答5，并假设其中1只兔子为红色，还有1只为蓝色，则说明森林里至少有红色兔子和蓝色兔子各6只。为最小化可能的兔子总数，我们假设这12只兔子都在这13只内。这时还有一只额外的兔子有着不同于红色和蓝色的颜色，则我们可以得到兔子的最少数目为18。

一般地，设有 $x$ 只兔子回答 $y$ ，则至少有 $\lceil{\frac{x}{y+1}}\rceil$ 种不同的颜色，且每种兔子有 $y+1$ 只。因此兔子数目至少为 $\lceil{\frac{x}{y+1}}\rceil\times(y+1)$ 。

Rabbits that share the same color should answer the same number; conversely, if 2 rabbits answer differently, they must not be the same color. Thus, here we apply a hash table to partition rabbits with the same number of response into the same group, then calculate the minimun number of rabbits for each group and add the result to the final answer.

For example, there are 13 rabbits answer "5", and assuming that one of them is red and one is blue, we would mean that there are at least 6 red and 6 blue rabbits each in the forest. To minimize the total number of rabbits, we suppose that all 12 rabbits are within these 13, and there is an extra rabbit whose coler is neither red nor blue. Therefore, we can conclude that the minimum of rabbits in this forest is 18.

Generally, let $x$ rabbits answer $y$ , then there are at least $\lceil{\frac{x}{y+1}}\rceil$ colors and there are $y+1$ rabbits of each color. Thus, the minimum number of rabbits that could be $\lceil{\frac{x}{y+1}}\rceil\times(y+1)$ in the forest.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(n)$

Code

func numRabbits(answers []int) int {
	var ans int
	freq := map[int]int{} // answers[i]: count
	for _, y := range answers {
		freq[y]++
	}
	for y, x := range freq {
		ans += (x + y) / (y + 1) * (y + 1)
	}
	return ans
}

Reference

1. 森林中的兔子