Daily Leetcode 781: Rabbits In Forest
Funniest question on leetcode so far
Difficulty: medium
The Question
https://leetcode.com/problems/rabbits-in-forest/description/?envType=daily-question&envId=2025-04-30
There is a forest.
In the forest, there are an unknown number of rabbits.
We ask n rabbits: How many other rabbits have the same color as you?
We then collect their answers in answers: list[int], where answers[i] is the the answer of the i_th rabbit.
Given answers: list[int], write a function that returns the minimum number of rabbits that could be in the forest.
Assumptions
rabbits have many different colours and can talk
all rabbits are 100% truthful
let’s consider some cases
Case 1) single numbers
given [1]:
rabbit 0: 1 other rabbit has the same colour as me
as such, there are minimally 1 + 1 = 2 rabbits
given [5]:
rabbit 0: 5 other rabbits have the same colour as me
as such, there are minimally 5 + 1 = 6 rabbits
given [120]:
rabbit 0: 120 other rabbits have the same colour as me
as such, there are minimally 120 + 1 = 121 rabbits
Case 2) Different numbers
Given [1, 2, 3]:
rabbit 0: 1 other rabbit has same colour as me => minimum 2 rabbits
rabbit 1: 2 other rabbits have same colour as me => minimum 3 rabbits
rabbit 2: 3 other rabbits have same colour as me => minimum 4 rabbits
total minimum number of rabbits = 2 + 3 + 4 = 9
Given [5, 10]:
rabbit 0: 5 other rabbits have same colour as me => min 6 rabbits
rabbit 1: 10 other rabbits have same colour as me => minimum 11 rabbits
total minimum number of rabbits = 6 + 11 = 17
Case 3) Multiple of the same number
Given [3, 3]:
rabbit 0: 3 other rabbits have same colour as me
rabbit 1: 3 other rabbits have same colour as me
since we’re considering the minimum number of rabbits, it is possible that rabbit 0 and rabbit 1 have the same colour
as such, minimum number of rabbits = 3 + 1 = 4
Given [10, 10, 10]:
rabbits 0, 1, 2: 10 other rabbits have same colour as me
it is possible that rabbits 0, 1 and 2 have the same colour
as such, minimum number of rabbits = 10 + 1 = 11
Case 4) Multiple of the same number, but exceeding limits
Given [1, 1, 1, 1]:
rabbits 0, 1, 2, 3: 1 other rabbit has the same colour as me
but it is NOT possible that rabbits 0, 1, 2, 3 have the same colour
what is possible: rabbits 0 and 1 have same colour, rabbits 2 and 3 have same colour
the value
1means a maximum of 2 rabbits have the same colouras such, min number of rabbits = (1 + 1) + (1 + 1) = 4
Given [2, 2, 2]:
rabbits 0, 1, 2: 2 other rabbits have the same colour as me
it is possible that rabbits 0, 1, 2 have the same colour
min number of rabbits = 2 + 1 = 3
Given [2, 2, 2, 2]:
rabbits 0, 1, 2, 3: 2 other rabbits have the same colour as me
it is NOT possible that rabbits 0, 1, 2, 3 have the same colour
case 1: (0, 1) and (2, 3) have the same colour
case 2: (0, 1, 2) have the same colour
in either case, min number of rabbits = (2 + 1) + (2 + 1) = 6
More examples:
[1, 1] => 2
[1, 1, 1] => 4
[1, 1, 1, 1] => 4
[1, 1, 1, 1, 1] => 6
[2, 2, 2] => 3
[2, 2, 2, 2] => 6
[2, 2, 2, 2, 2] => 6
[2, 2, 2, 2, 2, 2] => 6
[2, 2, 2, 2, 2, 2, 2] => 9Case 5: 0 rabbits have same colour as me
if a rabbit says 0 rabbits have the same colour as me, it means that he is the only one with that certain colour.
The approach
count the frequency of each number in
arrayfor each number, calculate the minimum number of rabbits for that number
return the final sum
The Code
Overall time complexity: O(n)
Conclusion
Hopefully this was clear and easy to understand
If You Wish To Support Me As A Writer
Buy my book — 101 Things I Never Knew About Python at https://payhip.com/b/vywcf
Clap 50 times for this story
Leave a comment telling me your thoughts
Highlight your favourite part of the story
Thank you! These tiny actions go a long way, and I really appreciate it!
LinkedIn: https://www.linkedin.com/company/the-python-rabbithole/