Rabbits In Forest

Easy
0/40
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in companies
Flipkart limitedDP World

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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
Sample Input 1 :
2
3
2 2 2
4
0 1 1 0
Sample Output 1 :
3
4
Explanation of Sample Input 1 :
For the first test case:


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.

For the second test case:


'ANSWERS[0]' and 'ANSWERS[3]' indicate that there exist two rabbits rabbit 1 and rabbit 4 which don't have the same color as any other rabbit. So, there are at least two rabbits.
Now rabbit 2 and rabbit 3 tell that there is one more rabbit precisely like them (as indicated by 'ANSWERS[1]' and 'ANSWERS[2]').   
Therefore, they can be of the same color.
Sample Input 2 :
2
3
1 1 2
4
1 1 2 2
Sample Output 2 :
5
5
Hint

Can we use a hash map?

Approaches (1)
Hash Map

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.
Time Complexity

O(N), where ‘N’ is the length of the given array/list ‘ANSWERS’.

 

We have to traverse the array completely. Therefore, net time complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the length of the given array/list ‘ANSWERS’.

 

Since we are using a map to keep track of the elements.

Code Solution
(100% EXP penalty)
Rabbits In Forest
Full screen
Console