~/leetcode $ 781. Rabbits-In-Forest

Rabbits are cool creatures. My first intuition was to get the number of rabbits that have x rabbits with the same colour as them.

Once we get these counts, we are able to calculate the minimum number of rabbits that could be in the forest. There are two main cases: The count hashmap is a map that has the x as the key and the number of rabbits that say x as the values.

We can see that the number of minimum rabbits needed to satisfy a given entry in the hashmap is equal to the (value divided by key + 1 rounded up) all multiplied by key + 1.

For example: If we had 5 rabbits saying that there are 2 other rabbits, we would have the entry of { 2: 5 } in the hashmap.

Then in order to satisfy this requirement, we can assume that 3 of the rabbits are part of the same group (3 rabbits will each say there are 2 other rabbits with same color) and so there are 2 rabbits that also belong to a different group (we can assume these 2 rabbits belong to the same belong).

Therefore, to satisfy this entry, we need 2 groups of rabbits with each group having 3 rabbits, totaling 6 rabbits.

We can do this for all the entries in the hashmap and return the resulting total.

class Solution(object):
    def numRabbits(self, answers):
        """
        :type answers: List[int]
        :rtype: int
        """
        res = 0
        count = Counter(answers)
        for key, value in count.items():
            n = key + 1
            groups = (value + n - 1) // n
            res += groups * n

        return res

Time Complexity: O(n)

Space Complexity: O(n)

Time Taken: 7m 26s