Skip to content

← leetcode

Rabbits in Forest

· Medium

LeetCode problem 781

After going through some test-cases, it is evident that there is a pattern present; if we let answers[i] = n and let the number of rabbits that return n be count:

  • if count % (n+1) != 0, that implies that there exists a minimum (n+1) - (count % (n+1)) rabbits that are not present
    • this is because we can group all the rabbits that returned n into count // (n+1) groups
    • then, that implies that the count % (n+1) must be the remainder of a pre-existing group, and there must be (n+1) - (count % (n+1)) rabbits that are not present
  • else, if count % (n+1) != 0, that implies that the minimum number of rabbits of the same colour are all present

code

class Solution {
public:
    int numRabbits(vector<int>& answers) {
        unordered_map<int, int> mp;
        for (int n : answers) {
            ++mp[n];
        }
        int ans = 0;
        for (auto &[key, value] : mp) {
            if (value % (key+1) != 0) {
                ans += value - (value % (key + 1)) + key+1;
            } else {
                ans += value;
            }
        }
        return ans;
    }
};

complexity

  • Time: O(n+m), where n is the number of elements in answers and m is the number of unique elements in answers
  • Space: O(m)

time taken

  • like less than 5 minutes