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