Rabbits in Forest Problem Solved (C++, Java, Python)

Counting the frequency of the numbers in an array can be done by maps. The map is a data structure that stores key and value pairs. It helps you to easily count the frequency, to get value from the key, etc. In this article, we will discuss the famous leetcode problem called the Rabbits in Forest.

Rabbits in Forest Problem Explained

In the Rabbits in Forest problem, we are given an array that contains some rabbits’ answers to the question, “How many rabbits have the same color as yours”. We have to count the minimum number of rabbits present in the forest.

Note that the Array size may be less than the total number of rabbits. Let’s understand this with an example:

Input:  [0, 2, 1, 1]

Output: 6

The answer will look like this:

1. First rabbits say 0, which means no rabbits have the same color as him. Let’s assume his color is white so the total number of white rabbits in the forest is 1.
2. The second rabbit says 2, let’s assume his color is brown which means 2 more rabbits are having the color brown.
3. The third one says 1, which means this rabbit has a different color than brown and white because if this color is brown, he also sees 2 brown rabbits. If his color is white then there will be two rabbits in the forest having color white. So its color will be different than brown and white. Let’s assume the color is green. So there will be 2 green rabbits.
4. The fourth one says 1, it cannot be brown and white as discussed, So let us assume his color is green then it must see one more green rabbit as the green rabbit count is 2.
5. So the total number of rabbits is 1 white + 3 brown + 2 green  = 6.

Another similar question about removing duplicate elements from an array, a 4-sum problem, etc., using a map.

Hash Map Approach

Let’s assume you have an array [1, 1, 1, 1], which means you have 2 rabbits of the same color white, and 2 rabbits of the same color green. This can also be observed by finding the number of rabbits with the same value as a[i].

Now, find their remainder when you divide this count by a[i]+1. Add this remainder to the count. Then, add the count to the answer variable.

Let’s take an example:

• Create an unordered_map that stores the frequency of each value in the array.
• Iterate over the map and check how many extra rabbits are required that are not in the array by calculating the remainder.
• Add this remainder into the frequency and add this frequency into the ans variable.
• Return the ans variable.

The time complexity for the above process is O( n log(n) ) as we are storing the value into the map which requires log(n) time complexity. We are iterating over the loop that took O(n) time complexity. The space complexity will be O(n) as we are storing values on the map.

You can also find the intersection of two arrays using hashmap.

Optimize Sorting Approach

As mentioned above, we are using O(n) space complexity to store all the values in the array. This can be reduced if we sort the array and count the values till they are the same and then find the remainder. In that case, we do not have to store the values in the map and our space will reduce to O(1).

Let’s examine this approach:

1. Sort the given array.
2. Create a variable count that stores the frequency of the same value in the array
3. Iterate over the array and keep increasing the count with 1 if the value of the current index is equal to the value at the next index.
4. If values are not the same, then find the remainder of this count with the current value of the array i.e. count % (a[i] + 1).
5. Add this remainder into the count variable and this count into the ans variable.
6. Again update the count to 1 and continue the same process.
7. Return the ans once the loop is over.

Let’s examine the code for the above process.

C++ Code

Here is the solution implemented in C++ for Rabbits in Forest problem:

#include<bits/stdc++.h>
using namespace std;

int main(){

    vector<int> arr = {1, 1, 2, 0, 1};
    // sort the given array
    sort(arr.begin(), arr.end());

    // count variable for count the frequency of the same elements.
    int count  = 1;
    // ans variable which stores total rabbits and n stores the size of the array.
    int ans = 0, n = arr.size();

    for(int i=0; i<arr.size(); i++ ){
        
        if(i == arr.size()-1 || (arr[i]!=arr[i+1])){
            // find remainder.
            int rem = count%(arr[i]+1);
            if(rem) ans = ans + (arr[i]+1) - rem;
            count = 1;
        }else{
            // if current and next values are not same increment our count variable.
            count = count + 1;
        }
    }
    
    ans = ans + n;
    cout<<ans<<endl;
    return 0;
}

Java Code

We can program it with Java also:

import java.util.*;

class RabbitsInForest {
    public static void main(String[] args) {
        List<Integer> arr = new ArrayList<>(Arrays.asList(1, 1, 2, 0, 1));
        
        // Sort the given array
        Collections.sort(arr);

        // Count variable for counting the frequency of the same elements.
        int count = 1;
        // Ans variable which stores total rabbits and n stores the size of the array.
        int ans = 0;
        int n = arr.size();

        for (int i = 0; i < arr.size(); i++) {
            if (i == arr.size() - 1 || arr.get(i) != arr.get(i + 1)) {
                // Find remainder.
                int rem = count % (arr.get(i) + 1);
                if (rem != 0) ans += (arr.get(i) + 1) - rem;
                count = 1;
            } else {
                // If current and next values are not same increment our count variable.
                count++;
            }
        }

        ans += n;
        System.out.println(ans);
    }
}

Python Code

Below is the Python program for the sorting approach:

arr = [1, 1, 2, 0, 1]

# Sort the given array
arr.sort()

# Count variable for counting the frequency of the same elements.
count = 1
# Ans variable which stores total rabbits and n stores array size.
ans = 0
n = len(arr)

for i in range(len(arr)):
    if i == len(arr) - 1 or arr[i] != arr[i + 1]:
        # Find remainder.
        rem = count % (arr[i] + 1)
        if rem:
            ans += (arr[i] + 1) - rem
        count = 1
    else:
        # If current and next values are not same increment our count variable.
        count += 1

ans += n
print(ans)

Output:

8

The time complexity for the Sorting approach to solving the Rabbits in Forest problem is O( n log(n) ). We are iterating over a loop whose time complexity does O ( n ) so overall complexity becomes O( n log(n) ). Space complexity will be reduced to O(1) as no extra space is used. 

We can compare both the approaches to see how we optimized it:

Conclusion

In this article, we learned about hash maps and sorting functions to solve the Rabbits in Forest problem from leetcode. Some of the similar programming problems you can solve are the Majority Element problem, Valid Anagram, or Alien Dictionary problem, to brush up your skills.