781. Rabbits in Forest

Time: O(n)

Space: O(n)

Intuition

Rabbit says "x others have my color" → group of x+1 same-colored rabbits. Greedily pack rabbits into groups of size x+1.

Algorithm

1Frequency count: freq[x] = how many rabbits said x.
2For each x: groups = ceil(freq[x] / (x+1)). Add groups*(x+1) to answer.

Example Walkthrough

Input: [1,1,2]

1.x=1: freq=2, groups=ceil(2/2)=1 → 2 rabbits. x=2: freq=1, groups=ceil(1/3)=1 → 3 rabbits. Total=5.

Output: 5

Common Pitfalls

•Use ceiling division: (freq[x] + x) / (x+1).

781.cs

// Approach: Count each reported answer value; for each distinct answer a, group size = a+1, and we need ceil(count / (a+1)) full groups.
// Time: O(n) Space: O(n)

public class Solution
{
    public int NumRabbits(int[] answers)
    {
        int ans = 0;
        int[] count = new int[1000];

        foreach (int answer in answers)
        {
            if (count[answer] % (answer + 1) == 0)
                ans += answer + 1;
            ++count[answer];
        }

        return ans;
    }
}

Was this solution helpful?