Show problems as
Classic problem #781MediumArrayHash TableMathGreedy

Rabbits in Forest

Real-world version: The Fewest Moths in the Jar
Tracked in this browser only
Read Rabbits in Forest on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Some of the moths in a jar were asked how many other moths share their own pattern, and replies holds the answers given, one per moth asked. Moths that were not asked said nothing.

A moth answering x belongs to a group of exactly x + 1 moths sharing one pattern, and moths in different groups never share a pattern.

Return the fewest moths the jar could hold.

Examples

Example 1

Input
replies = [1, 1, 1]
Output
4

Two of the three moths can share a group of two, but the third needs a group of two of its own, so a fourth moth must be there unasked.

Example 2

Input
replies = [0, 1, 2, 3]
Output
10

Each answer names a different group size, so the four groups hold one, two, three and four moths.

Example 3

Input
replies = [2, 2, 2, 2]
Output
6

Groups of three are named. Three of the four moths fill one group and the fourth opens another, which needs two more moths to fill it.

Constraints

  • 1 <= replies.length <= 1000
  • 0 <= replies[i] < 1000

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def num_rabbits(replies: list[int]) -> int:
Java
public int numRabbits(int[] replies)

More on the same topics