https://leetcode.com/problems/rabbits-in-forest/description/
initial
I almost got it but I couldnt figure out how to handle logic when v%(i+1) != 0.
If we have v rabbits all answering i, and v is not a multiple of i + 1, we have v//(i+1) full groups, and the remaining rabbits must form an additional group of size i + 1. So the logic is
(v//(i+1) +1) * (i+1) rabbits = total rabbits.
from collections import Counter
class Solution:
def numRabbits(self, answers: List[int]) -> int:
# 1,2,2 = 5
# r b b [hidden=r,b]
# 1,2,2,2 = 5
# r b b b [hidden = r]
# 1,2,2,2,2 =5+3
# r b b b x [hidden=r,x,x]
# 1,2,2,2,2,2 = 6+2
# r b b b x x [hidden=r,x]
# 1,2,3 =3+6
# r b x [hidden=r,b,b,x,x,x]
# 1,1,2 =5
# r r b [hidden=b,b]
# 10,10,10 = 3+8
# r r r [hidden=8 rs]
# 1,1,1 = 3+1
# r,r,b [hidden=b]
count = Counter(answers)
ans=0
for i,v in count.items():
if v % (i+1)==0:
ans+= v
else:
ans += (v // (i+1) +1) * (i+1)
return ans
complexity
Time Complexity: O(n)
Space Complexity: O(number of unique answers) (which is ≤ O(n))
