781: Rabbits-in-Forest
Medium
table of contents
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:
:::sidebar - 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;
}
};