Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

An answer of k means the speaker belongs to a color group of exactly k + 1 rabbits, including itself. Equal answers can share a group only up to that size, while different answers cannot describe the same color. Minimizing the total means packing equal answers into as few complete groups as possible.

Approach

Count how many rabbits gave each answer k.
For frequency f, form ceil(f / (k + 1)) groups and contribute that count multiplied by k + 1. Any unfilled places represent rabbits that were not asked.
An answer of zero contributes one rabbit per occurrence, since each must have a unique color.
Sum all contributions. Rounding upward is necessary even for a partially represented final group because every reported group must contain its full stated number.

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        res = 0
        map = defaultdict(int)

        for a in answers:
            map[a] += 1

        for k in map:
            # 1. answers are 0
            if k == 0:
                res += map[k]
            # 2. answers are not 0
            else:
                #rounded up full cycles of (k + 1)
                res += ceil(map[k] / (k + 1)) * (k + 1)

        return res

Complexity analysis

For n answers and u distinct answer values, counting and aggregating groups takes O(n + u) time and O(u) auxiliary space.