Last Updated: 13 Apr, 2021
Rabbits In Forest
Easy
Asked in companies
In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those answers are placed in an array/list named ‘ANSWERS.’
Return the minimum number of rabbits that could be in the forest.
For Example :
Given:-
‘N’ = 3, ‘ANSWERS’ = [2,2,2]
There are a total of 3 rabbits because each of the ‘ANSWERS[i]’ tells that there are two more rabbits just like them with the same color.
Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains a single integer, ‘N’, where ‘N’ is the number of elements of the array.
The second line of each test case contains ‘N’ space-separated integers, denoting the elements of 'ANSWERS'.
Output Format :
For each test case, print an integer denoting the total number of rabbits.
The output of each test case will be printed in a separate line.
Note :
You don’t need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= N <= 5000
1 <= ANSWERS[i] < 1000
Where ‘ANSWERS’[i] is the array element at index ‘i’.
Time limit: 1 sec
Approaches
The main idea is that if ‘X’ + 1 rabbits have the same color, then we get ‘X’ + 1 rabbits who all answer ‘X’ i.e ‘ANSWERS[i]’ = ‘X’ for ‘X’ + 1 rabbits. Now ‘N’ rabbits answer ‘X.’
- If ‘N’ % (‘X’ + 1) == 0, we need ‘N’ / (X + 1) groups of ‘X’ + 1 rabbits.
- If ‘N’ % (‘X’ + 1) != 0, we need ‘N’ / (‘X’ + 1) + 1 groups of ‘X’ + 1 rabbits.
Thus, the number of groups is ceil(‘N’ / (‘X’ + 1)).
Algorithm:
- Maintain a map ‘FREQTABLE’ which stores the frequency of each number.
- Now traverse the ‘FREQTABLE’:
- The ‘RABIT’ variable tells the number of rabbits that have frequency ‘FRQ’.
- Maintain a variable ‘RES’ that stores the total number of rabbits.
- Add (‘FRQ’ + ‘RABIT’) / (’RABIT’ + 1) * (’RABIT’ + 1) to the ‘RES’.
- Return ‘RES’ as the final answer.