781. Rabbits in Forest #

Problem #

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].

Summary #

In a forest, each rabbit has a color. Some rabbits (possibly all of them) tell you how many other rabbits have the same color as themselves. We place these answers in the answers array. Return the minimum number of rabbits in the forest.

Notes:

• The length of answers is at most 1000.
• answers[i] is an integer in the range [0, 999].

Solution Ideas #

• Given an array, each element represents how many rabbits of the same kind a rabbit says there are. The task is to output the total number of rabbits. It is possible that the number reported by the rabbits is less than the total number of rabbits.
• The key to this problem is how to divide rabbits of different types. It is possible that the number of rabbits of the same type is the same, for example [2,2,2,2,2,2], which actually represents 3 types and a total of 6 rabbits. Use a map to deduplicate rabbits of the same type, continuously decrementing the count. When the count for a type of rabbit becomes 0, if there are still rabbits of that type reporting numbers, they need to be treated as another type of rabbit.

Code #

package leetcode

func numRabbits(ans []int) int {
	total, m := 0, make(map[int]int)
	for _, v := range ans {
		if m[v] == 0 {
			m[v] += v
			total += v + 1
		} else {
			m[v]--
		}
	}
	return total
}