Computer Science
Updated 17 days ago | GitHub

Rabbits In The Forest

Problem Highlights

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Can I see what color the rabbits are?
    • No
  • What are the constraints?
    • 1 <= answers.length <= 1000
    • 0 <= answers[i] < 1000
  • If there are fewer than i + 1 answers of i, they could be the same color
    • There could be a group of 2 rabbits who say “1”
    • There could be a group of 3 rabbits who say “2”
  • If a rabbit says:
    • 0: add 1 to our count every time
    • 1: add 2 to our count every two rabbits
    • 2: add 3 to our count every 3 rabbits
    • n: add n+1 to our count every n rabbits
HAPPY CASE
Input: answers = [1,1,2]
Output: 5

EDGE CASE
Input: answers = [10,10,10]
Output: 11

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

  • Greedy Algorithm: Greedily put as many rabbits into the same color as possible, until it is not possible to fit, create a new color. If rabbits share the same answer x, we can put at most x+1 rabbits in this color group. Because the result is min of rabbits count, so put as many rabbits in same color group as possible.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

1. Create a hashtable counts
2. Set sum = 0
3. For each answer in answers
If answer == 0, sum += 1
If answer not in counts:
counts[answer] = 1
sum += answer + 1
If counts[answer]  < answer + 1
counts[answer] ++
else
counts[answer] += 1
sum += answer + 1
4. Return sum

⚠️ Common Mistakes

  • What are some common pitfalls students might have when implementing this solution?

To minimize the total number of rabbits, we can divide these y rabbits into groups, each group having a size of (x+1) and the rabbits within the same group having the same color. If y%(x+1)>0, then the last y%(x+1) rabbits have the same color as some other rabbits that don’t share their information in this poll. These last y%(x+1) and those rabbits that don’t participate should add up to (x+1) (Otherwise, the claim that x other rabbits have the same color is a false claim).

4: I-mplement

Implement the code to solve the algorithm.

class Solution(object):
    def numRabbits(self, answers):
        count = collections.Counter(answers)
        return sum(-v % (k+1) + v for k, v in count.items())

class Solution {
    public int numRabbits(int[] answers) {
        int[] count = new int[1000];
        for (int x: answers) count[x]++;

        int ans = 0;
        for (int k = 0; k < 1000; ++k)
            ans += Math.floorMod(-count[k], k+1) + count[k];
        return ans;
    }
}

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

  • Trace through your code with an input to check for the expected output
  • Catch possible edge cases and off-by-one errors

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

  • Time Complexity: O(N), where N is the number of rabbits that answered
  • Space Complexity: O(N)