Code not giving Desired output (Migratory Birds – HackerRank)

Tags:



The Question is here

https://www.hackerrank.com/challenges/migratory-birds/problem

I have tried out the following code which does not work with a particular test case . The test case is here

https://hr-testcases-us-east-1.s3.amazonaws.com/33294/input04.txt?AWSAccessKeyId=AKIAJ4WZFDFQTZRGO3QA&Expires=1580486031&Signature=2XwAz3pdGmZVcNC1YpHk7buPl5U%3D&response-content-type=text%2Fplain

My code is

static int migratoryBirds(List<Integer> arr) {
    List<Integer> typesofbirds = new ArrayList<>();
    List<Integer> noofbirds = new ArrayList<>();
    for(int i=0;i<arr.size();i++){
        if(i==0){
            typesofbirds.add(arr.get(i));
        }
        else{
            for(int j=0;j<typesofbirds.size();j++){
                if(j==typesofbirds.size()-1 && typesofbirds.get(j) != arr.get(i)){
                    typesofbirds.add(arr.get(i));
                }
                else{
                    if(typesofbirds.get(j) == arr.get(i)){
                        break;
                    }
                }
            }
        }
    }

    System.out.println(typesofbirds);
    for(int i=0;i<typesofbirds.size();i++){
        int count=0;
        for(int j=0;j<arr.size();j++){
            if(typesofbirds.get(i) == arr.get(j)){
                count++;
            }
        }
        noofbirds.add(count);
    }
    System.out.println(noofbirds);

    int maximumbirdsindex=0;
    for(int i=1;i<noofbirds.size();i++){
        if(noofbirds.get(i)>noofbirds.get(maximumbirdsindex)){
            maximumbirdsindex=i;
        }
    }
    return typesofbirds.get(maximumbirdsindex);
}

The array typesofbirds contains the different type of birds id order wise

The array noofbirds contains the no of birds corresponding to each bird type order wise

maximumbirdsindex contains the index of the bird corresponding to the array typesofbirds

first for loop fills the array typesofbirds the second loop fills the noofbirds array and the third loop simply calculates the index of the maximum birds id

Answer

You need to do two things: Count the number of birds for each type, and then find the maximum. While you are trying to do that, you seem to be running into an issue of getting lost in your code by making it over-complicating it. Think about this: how many birds you could count and know which number that is all in the same data structure?

Just 1 array could accomplish this really well for you. You increment the correct index of the array each time you count, and then by going in order you can determine which bird is the highest number of sightings, and that index is the correct number.

If you want to try and debug it on your own with that thought process then that’s great. If you want to see a working implementation it is below(feel free not to check it out until after you have done it yourself).

  static int migratoryBirds(List<Integer> arr) {
    int[] birdCountArr = new int[6]; // bird numbers are guaranteed to be between [1,5], we ignore index 0.
    for(int n : arr) {
      birdCountArr[n]++;
    }
    int high = 0;
    int highBirdNum = 0;
    for(int i = 1; i < birdCountArr.length; i++) {
      if(birdCountArr[i] > high) {
        high = birdCountArr[i];
        highBirdNum = i;
      }
    }
    return highBirdNum;
  }

EDIT: A little more explanation to follow up on your question. In the first loop we are simply going through the list of ints we are given and putting them into the array we made based on the index. If the bird is “4”, we put it into index 4. So let’s say we have this input: 1 1 2 1 3 4 4 5 2 We are going to get each number from this list and put it into the array based on index. So our array would look like this: [0, 3, 2, 1, 2, 1] We have 0 birds of number 0(since that’s not valid), 3 birds of number 1, 2 birds of number 2, 1 bird of number 3, 2 birds of number 4, and 1 bird of number 5. The correct answer in this case would be 1, since that is the bird with the highest number.

Essentially, index = bird number, which index is highest, if there are multiple indexes with the same number, lowest index wins 🙂



Source: stackoverflow