# Migratory Birds

# Migratory Birds

AbhishekVermaIIT + 30 comments Since a lot of codes shared are complicated as well as sub-optimal. Here's a simple, concise and optimal approach for coders looking for an elegant solution :

input() count = [0]*6 for t in map(int,input().strip().split()): count[t] += 1 print(count.index(max(count)))

The solution is

**O(n)**and traverses the given list only once.

### For aspiring programmers :

Be careful while learning from the codes you read. I haven't checked for all languages, but a lot of python-codes here, are even

**incorrect**(including the**editorial**as well as currently topvoted comment). Particularly for this problem, be cautious if you see usage of "set", "dictionary" or "Counter" anywhere.Dictionaries/sets are unordered in python, which means one cannot trust the outcome where order matters. In fact, these solutions would always give wrong result for simple testcase like

`2, 2, 1, 1`

in Python 3.6. Thus, as programmers we need to ensure that our code succeeds always, and not only by chance !nkedia1234 + 0 comments [deleted]vikramkhalsa + 0 comments Came up with the exact same solution. Thanks for the warning message as well.

chiwawa_tt + 1 comment I am wondering what kind of data structure of count[] using in the code? And thanks for the warning, it does make sense.

AbhishekVermaIIT + 1 comment The variable

`count`

in the code is usual python-list (initialized to 0).The statement

`count = [0]*6`

is short for`count = [0,0,0,0,0,0]`

.shivamsonu23 + 1 comment I am wondering why count is initialized with [0]*6 and how count[t] not leading to any boundary error?

helloworldbye + 0 comments count will have index 0-5, and t will be type 1-5, which will not exceed the boundary.

tanmaysankhe + 1 comment can anyone explain me last print statement...thanks in advance

AbhishekVermaIIT + 1 comment For the convenience, let's break the statement into equivalent code :

maxVal = max(count) ans = count.index(maxVal) print(ans)

Now

`maxVal`

stores the maximum value in the array`count`

using the function`max()`

. In second line, we are using the method`index()`

. The index() method finds the given element in a list and returns its lowest index. So, here it finds`maxVal`

in the list`count`

and stores the location of its first occurence in`ans`

. The last line just prints`ans`

.mghebran + 1 comment Your statement "The solution is O(n) and traverses the given list only once. " is not true. While you are explicitly traversing the list only once, the functions max() and index() both implicitly traverse the list in order to perform their function.

AbhishekVermaIIT + 0 comments Please read it carefully again, it indeed traverses the

**given list**only once.The functions

and`max()`

are applied on constant size list`index()`

(size only 6) !`count`

yabueh + 0 comments What a brilliant solution. I love it.

gabriellomba + 2 comments I did it similarly to you at first but then I tried to optimize it from

**O(2n)**(for loop and list.index()) to**O(n)**and came up with this:def migratoryBirds(n, ar): ids = [0] * 5 maxN = 0 id = 1 for i in range(n): ids[ar[i] - 1] += 1 if(ids[ar[i] - 1] > maxN): maxN = ids[ar[i] - 1] id = ar[i] elif(ids[ar[i] - 1] == maxN and ar[i] < id): id = ar[i] return id

AbhishekVermaIIT + 1 comment It is not true. I would like to mention few things to not mislead anyone.

â€¢ O(n) is same as O(2n), please refer definition in case of confusion.

â€¢

**n**refers to the size of input. The for-loop is O(n) because running time varies as the size of input "n" changes.â€¢ list.index() is

**not**O(n), but O(1). The`index`

method is applied on a constant size (size=6) list. It can also be understood by the fact that its running time is independent of the size of input**n**.â€¢ It is not preferred to have so many conditions inside any loop when they can be avoided. Though it might not change complexity, yet it will definitely slow it down.

â€¢ This solution is, in fact,

**slower**than the solution in the main post because of the above mentioned reasons. You can verify it yourself. On my machine it is always slower by 40,000 micro-seconds or more for max input, which is considerable duration in terms of computer.

Now, for the coders learning from discussions, I would suggest that give importance to "readability" of the code. It matters a lot in professional environment. Though, here the scenario is reverse, but otherwise also it isn't adviced to compromize with readability to gain few micro seconds. "Zen of Python" gives a nice guideline, you can enter the following in python interpreter to read it:import this

gabriellomba + 0 comments Even though the conditions are intelligible, I get your points. In professional environment, though, the types of birds probably would be much bigger but that's mere speculation.

About the complexity part, did not mean to mislead anyone. I should've said

**O(n + m)**where**n**is size of input and**m**is types of birds. Thank you for correcting me on that part.

quangnguyenhuux1 + 0 comments thank you, i used c++ language and with algorithms find max yours

shreekar3430 + 1 comment n = int(input().strip()) ar = list(map(int, input().strip().split(' '))) a = ar.count(1) b = ar.count(2) c = ar.count(3) d = ar.count(4) e = ar.count(5) li=[a,b,c,d,e] print(1+li.index(max(li)))

what is the Time Complexity of this code?

AbhishekVermaIIT + 1 comment Time complexity is O(n), but it traverses the given list 5 times, hence it will be accordingly slower than the code in main post.

shreekar3430 + 0 comments Thanks.

djaychela + 1 comment This, to me, is what places like this should be all about - clear code which works, but also which points out features that others (like me) may not know about - the index method is really useful, and I'd not seen it before. My code did something similar, but used more code to do the same thing. Thanks for posting it and the comment.

AbhishekVermaIIT + 0 comments I'm glad that you found it helpful. Thanks a lot for the appreciation!

Lehonti + 0 comments Nice [0]*6 syntax! My algorithm is the same as yours, but not written in a Pythonic way...

DanYoo940 + 7 comments for those who are beginners, I barely know what log(n) is here I brought really simple answer, I passed all tests too. Feel free to ask me questions, but i guess you guyz already know

public static void main(String args[]){ Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[] arr = new int[5]; for(int i = 0;i<n;i++){ switch (scan.nextInt()){ case 1 : arr[0]++; break; case 2 : arr[1]++; break; case 3 : arr[2]++; break; case 4 : arr[3]++; break; case 5 : arr[4]++; break; } } int highest = 0; int answer = 0; for(int i = 0;i<arr.length;i++){ if(arr[i]>highest){ highest = arr[i]; answer= i+1; } } System.out.println(answer); }

LamaO3 + 0 comments [deleted]mariojsanchez15 + 0 comments Your code is very simple to follow. If you dont mind let me suggest a simple change for your first loop:

int[] birdsCounter = new int[ 5 ]; for( int bird : ar ) birdsCounter[ bird - 1 ]++;

upendra28 + 3 comments your code doesn't cover the condition :- if two or more types of birds are equally common, choose the type with the smallest ID number. Btw , there is no test case to check this either...

mariojsanchez15 + 1 comment The array is traverse in order. Therefore the smallest id will be picked in case of a

upendra28 + 0 comments Thanks !!

marko_vatovec + 1 comment There is a test case to check this, it's number 4. If you don't select the lowest ID, you'll fail on the last test case.

koraytugay + 0 comments @marko, do you think my solution is fine?

groote + 0 comments second test case is for that bro. check it again

sudhanaboina_ra2 + 0 comments [deleted]sudhanaboina_ra2 + 0 comments I have done using bucket concept. Except one test case all other are failing. Feedback needed:

` static int migratoryBirds(int[] ar) {

`int[] bucket = new int[5]; for(int i=0;i<ar.length;i++){ int j = 5-((ar[i])%5); bucket[j-1]++; // } int highest = 0; int answer = 0; for(int i = 0;i<bucket.length;i++){ if(bucket[i]>highest){ highest = bucket[i]; answer= i+1; } } return answer; } ````

Jayanshu + 0 comments this is 0(n) solution can u give me 0(logn) solution

aiswarya110498 + 0 comments simple and excellent code for beginners.

swhitlock410 + 3 comments Please let me know what you think of my code in C#.

`using System; using System.Collections.Generic; using System.IO; using System.Linq; public class Solution { #region Private Property /// <summary> /// Gets or sets the Length. /// </summary> private static int Length { get; set; } #endregion #region Methods /// <summary> /// Returns the Max count of birds. /// </summary> /// <param name='arr'></param> private static String migratoryBirds(String[] arr) { // Complete this function return arr.GroupBy(a => a).Select(b => new{ Bird = b.Key, Count = b.Count() }).OrderByDescending(c => c.Count).ThenBy(d => d.Bird).FirstOrDefault().Bird; } #endregion public static void Main(String[] args) { Length = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(migratoryBirds(Console.ReadLine().Split(' '))); } }`

admin198 + 0 comments [deleted]cziprzi + 0 comments For starters i was going with dictionary, but your solution gave me an idea.

static int migratoryBirds(int n, int[] ar) { return ar .GroupBy(x => x) .Aggregate((x, y) => x.Count() > y.Count() ? x : y) .Key; }

I love the grouping part.

audusheriffemor1 + 0 comments Don't you feel that creating regions in this code is you doing too much.

maxim_marquez + 1 comment Pretty cool!

DanYoo940 + 0 comments Thank you!!!!

AamirAnwar + 1 comment Question. Why is the list 'count' of length '6'? We only have 5 classes of bird types right? Also what does max(count) return when all classes of birds have equal occurences? Does it return the one with the smallest ID?

AbhishekVermaIIT + 0 comments The id of birds vary from 1 to 5. Since, count is 0-indexed, taking size 6 allows to have indices 1 to 5.

If multiple birds have equal occurences, say 34, then max(count) returns 34. The "index" method applied on count (count.index(34) for this case) will return the smallest id.

programaths + 0 comments Your code is doing more than this one:

input() count = [0]*6 for t in map(int,input().strip().split()): count[t] += 1 maxIndex = 0 for i,v in enumerate(count): if v>count[maxIndex]: maxIndex = i print(maxIndex)

The reason is that your code is looking for the maximum the looking again to retrieve the index:

`count.index(max(count))`

The code I wrote skip one loop by working directly with the index.

It shows also that when you want efficience, you may have to sacrifice legibility.

So, for the given problem, your solution ace it. For a more general situation, one has to be warry that you implement something very specific to the problem at hand:

- Fixed number of bird Ids that are consecutive
- Ids are numeric

Would break if "names" where given instead of Ids or if ther was a lot of Ids.

The code you provided is well suited for small diversity of bird tagged by numerical ids.

okadahiroshi + 3 comments I have another solution, I think It is also correct and eazy.

def migratoryBirds(n, ar): m = [4,3,2,1,0] for b in ar: m[b-1] += 10 return 5 - max(m) % 10

programaths + 1 comment Why not

def migratoryBirds(n, ar): m = range(5) for b in ar: m[b-1] += 10 return max(m) % 10

It should work,but it is very specific!

okadahiroshi + 1 comment If two ID of birds are the same number the smaller ID wins. So the array

`m`

must be initialized in descending order.Of course, you can write

list(range(4, -1, -1))

or

list(reversed(range(5)))

If there were many kinds of birds I would have written so. But for this specific case [4, 3, 2, 1, 0] is easier to read.

I just avoid premature generalization.

programaths + 0 comments Good! Forgot that one :-\

AbhishekVermaIIT + 0 comments Well written Mr. Hiroshi ! This is actually nice alternative.

Thanks for sharing !nowyouseeme777o + 0 comments can you explain this code

cu_16bcs2416 + 0 comments don't you get tired of writing" elegant code, concise code, optimal code blah blah and blah". just put the damn code, explain it and that's it.. story over!!

koraytugay + 0 comments Why do you need the map? What is wrong with:

def build_bird_freq(arr: list): bird_freq = [0, 0, 0, 0, 0, 0] for i in range(len(arr)): bird_freq[arr[i]] += 1 return bird_freq.index(max(bird_freq))

thirumoorthi205 + 0 comments Here is my O(n) inplace solution:

`static int migratoryBirds(int[] ar) { for(int i=0;i<ar.length;i++) ar[(ar[i]%10)-1] = ar[(ar[i]%10)-1]+10; int max = -1,q=0; for(int i=0;i<ar.length;i++){ if(max<ar[i]/10){ max = ar[i]/10; q=i+1; } } return q; }`

washimdas2013 + 0 comments Nice idea Sir ! I can say, you are actually encoding the array & then decoding it back.. great thought !

pepcmarques + 2 comments Even simpler and perhaps faster for a huge list:

return max(set(ar), key=ar.count)

thirumoorthi205 + 0 comments [deleted]thirumoorthi205 + 0 comments This is not an inplace solution because space complexity for list to set conversion in python is O(n) and its time complexity is also O (n).

chuppi_angadi + 0 comments [deleted]chuppi_angadi + 0 comments [deleted]TellMeWHhy + 0 comments This is so ingenious. As a Python beginner I am amazed to see how simple and elegant your solution is. Awesome stuff lol

sandeee1928 + 0 comments `max()`

is also a linear function, so your soluion will also traverses the list twice.gravito + 0 comments Thank you :). Sometimes, the simplest way is the best way, both in code and in life.

Pythonologist + 0 comments The "count" list must actually be of length max(given_list_elements)+1,as the index in python starts from '0'.The zeroth index value of count is never edited if the bird IDs start from '1'.However,that's not gonna affect the output.So it's ok : )

sammy9292 + 1 comment I didnt think of creating a counter list. Thank you for teaching me a new way

Pythonologist + 0 comments Happy coding... : )

praveen_sk159 + 1 comment Can anyone explain , why he used 6 here.

count = [0]*6 It may fail when the input list contains value more than 6

eg: [10,10,1,2,3,4]

AbhishekVermaIIT + 1 comment Input list won't ever contain such values. Please read the constraints in problem statement once again :

*"It is guaranteed that each type is 1, 2, 3, 4 or 5".*praveen_sk159 + 0 comments Thanks. Missed that statement.

dhruvvaghela17 + 0 comments Thanks for the warnming man. We need friends like you more!

soundarkumar + 19 comments My Java 8 Solution

static int migratoryBirds(int n, int[] ar) { // Complete this function int ary[] = new int[n]; for(int i = 0; i < n ; i++ ) ary[ar[i]]++; int max = 0,maxpos=0; for(int i = 0 ; i < n ; i++) { if(ary[i] > max) { max = ary[i]; maxpos = i; } } return maxpos; }

bijeli_papir + 0 comments great!

adithyakrishna_1 + 1 comment can you please explain in detail what the first for loop does?

abhayupadhyay + 1 comment first for loop is counting sort .. it means the value reapt in array ar the index value of ary will inc

eg: initialy the value of ary is zero ary[4]++; //index 4 value inc by 1

vitthalharsh99 + 0 comments can you explain this again

adithyakrishna_1 + 1 comment ok I found out the first for loop gives us the count of the respective elements in another array Example: ar[0] = 2; ar[1] = 4; ar[2] = 3; ar[3] = 2; ar[4] = 3; ar[5] = 1; ar[6] = 2; ar[7] = 1; ar[8] = 3; ar[9] = 3;

`ary[0] = 1; ary[1] = 1; ary[2] = 1; ary[3] = 2; ary[4] = 2; ary[5] = 1; ary[6] = 3; ary[7] = 2; ary[8] = 3; ary[9] = 4; but my doubt now is how did you come up with this logic about the first for loop??????`

rmadhusudan359 + 0 comments you can be relate this with the COUNT SORT ALGORITHM, it has the same logic for counting number of occurence of a number in an array.

Srivatshan_G_R + 0 comments Is there any advantage of:

Replacing 'n' space allocation in ary[] by '6' ?

Replacing 'n' in second for loop by '6' ?

as it is mentioned only '5' identity no's .

vova_rova + 0 comments int ary[] = new int[n]; can be replaced by

int ary[] = new int[5]; or int ary[] = new int[6];

to have the same indeces

vivek8649 + 0 comments Thanks man

SudeepN + 3 comments Nice solution. A little optimization.

static int migratoryBirds(int n, int[] ar) { // Complete this function int []arr = new int [6]; for(int id:ar){ arr[id]++; } int maxValue = 0; int maxPos=0; for(int i =1;i<6;i++){ if(arr[i]>maxValue){ maxValue = arr[i]; maxPos = i; } } return maxPos; }

ashikwajith + 3 comments can you please explain this line inside foreach: arr[id]++;

bbui1997 + 0 comments same as arr[id] = arr[id] + 1;

rajrubu_mohanty + 0 comments incrementing the count of id !

kd821 + 0 comments Its nothing but intialising the type array with all the values from 1 to 5 like {1,2,3,4,5};

dkkplk + 0 comments great

saiprasadrekha81 + 0 comments int maxvalue and minvalue will give the mmax and min value but not the count of max occuring element no.so how to get the count of max occuring element.

warriorshikhar + 0 comments **What is the problem with my solution?**static int migratoryBirds(int n, int[] ar) { int zero=0; int[] array=new int[5]; for(int i : ar){ array[i-1]++; } for(int i:array){ if(i==0) zero++; } return 5-zero; }

akhils693 + 0 comments [deleted]DanYoo940 + 0 comments what does arr[ar[i]]++ do?

abhayupadhyay + 0 comments sir i aslo did the same as you but i want to ask some thing there is one condition in question If two or more types of birds are equally common, choose the type with the smallest ID number.

according to this condition if the type 2 will repeat 3 time and the type 4 will aslo repeat 3 time than the smallest index value is 2 but the solution of your and my always return the index 4

can you please see it once .....??

moff132 + 0 comments Hey I have a doubt.Can you tell me where you are checking the condition if two birds have equal count then printing the bird smaller index count

And also your output will fail if u enter the input as

4 then 5 5 6 6

tocshark + 0 comments salute , maja aaaya.

hari_4698 + 0 comments Your

*ary[]*array can be of the size 6 instead of*n*trgiangvp3 + 0 comments You dont need a

`max`

variable. You can compare`ary[i]`

with`ary[maxpos]`

.pritkumar + 0 comments Hey brother, Could you please explain how's ary[ar[i]]++; does work; i don't get it. Because your answer of ary[ar[i]]++; 0 1 0 1 3 1

pritkumar + 0 comments Hey brother, Could you please explain how's ary[ar[i]]++; does work; i don't get it. Because your answer of ary[ar[i]]++; 0 1 0 1 3 1

rishabhmatharoo1 + 0 comments thank you sir

SEAS_Low_Levels + 1 comment Does this work with the last test case?

rishabhmatharoo1 + 0 comments Yes it is working With every time case

saxtouri + 4 comments Python oneline (not optimal, though)

print(sorted(reversed(list(set(types))), key=types.count)[-1])

f1r3byte + 0 comments [deleted]LeHarkunwar + 1 comment Did it similarly, but didn't pass all tests :P

vandanasohrab + 0 comments passes all

import sys

def migratoryBirds(n, ar): return (sorted(reversed(list(set(ar))), key=ar.count)[-1])

n = int(input().strip()) ar = list(map(int, input().strip().split(' '))) result = migratoryBirds(n, ar) print(result)

amitrajitbose9 + 0 comments Where is the hurry? Why the oneline stunt? Hahha! You're a pro!

Silphendio + 1 comment This... shouldn't work.

set() is a hashset and has no fixed order. it should be sorted() instead of list()

print(sorted(reversed(sorted(set(types))), key=types.count)[-1])

Because there are only 5 types of birds, it can just be

print(sorted(list("54321"), key=types.count)[-1])

Here's my solution:

input() types=input().split() print(-max((types.count(i),-int(i)) for i in set(types))[1])

Dimple151997 + 0 comments can u explain the code

nik_roby + 2 comments Using python collections FTW.

import sys from collections import Counter n = int(input().strip()) types = list(map(int, input().strip().split(' '))) birds = Counter(types) # Counts the array into a dictionary print(birds.most_common(1)[0][0])

jon_black + 1 comment It's worth adding that this is sub-optimal. The

`Counter`

constructor will iterate the list, then`most_common`

will sort it in reverse order using a heap.eric2013 + 0 comments I believe most_common acts on an dictionary with <= 5 key/value pairs. So... any inefficiency in this step is completely irrelevant.

steschuser + 0 comments Solved it like this as well. However, documentation says:

most_common([n]) Return a list of the n most common elements and their counts from the most common to the least. If n is omitted or None, most_common() returns all elements in the counter. Elements with equal counts are ordered arbitrarily

While most_common(1) gave me the corret id, the above seems to indicate that this doesnt have to be true.

jobingeorge + 5 comments int main(){ int n; scanf("%d",&n); int *types = malloc(sizeof(int) * n); for(int types_i = 0; types_i < n; types_i++){ scanf("%d",&types[types_i]); } // your code goes here int id[]={0,0,0,0,0}; for(int i = 0; i<n; i++) { id[types[i]-1]++; } int max=0,type= 0; for(int j=0; j<5; j++) { if(id[j]>id[max]) { max=j; } } printf("%d",max+1); return 0; }

TianzhiZhou + 1 comment could you explain

for(int i = 0; i<n; i++) { id[types[i]-1]++; }

is what meaning?

grslopes92 + 1 comment Basically, each member of the id array represents the number of times that each id appear, so

id[types[i]-1]++;

is incrementing that value.

TianzhiZhou + 1 comment nice,but why are you int type=0?

grslopes92 + 0 comments Probably it was by accident, since it's never used

HARSHRANABIT + 0 comments nice approach dude...

jon_black + 1 comment With an extra variable you can keep track of the position with the highest count, and remove the second loop.

lingbo19_tang + 0 comments Yes, it can be done like this:

int is_max(int a, int b) { return (a>b) ? 0 : 1; } int main(){ int n; scanf("%d",&n); assert(n >= 5); assert(n <= 200000); int *types = malloc(sizeof(int) * n); for(int types_i = 0; types_i < n; types_i++){ scanf("%d",&types[types_i]); } // your code goes here int *counts = malloc(sizeof(int) * n); int max_i = 0; int global_max = 0; for(int i = 0; i<n; i++) { counts[types[i]-1]++; if (is_max(global_max, counts[types[i]-1]) == 1){ global_max = counts[types[i]-1]; max_i = types[i]-1; } } printf("%d",max_i+1); free(types); free(counts); return 0; }

fedcel + 0 comments Unneded complexity: you had better only memorize the frequencies and remove the types pointer. And not freeing dynamically allocated memory is a bad practice.

h160040201 + 0 comments code is nice

thirumoorthi205 + 2 comments O(n) inplace solution:

`static int migratoryBirds(int[] ar) { for(int i=0;i<ar.length;i++) ar[(ar[i]%10)-1] = ar[(ar[i]%10)-1]+10; int max = -1,q=0; for(int i=0;i<ar.length;i++){ if(max<ar[i]/10){ max = ar[i]/10; q=i+1; } } return q; }`

15s105 + 0 comments Awesome

srijandeep31 + 1 comment please explain me ur code

srijandeep31 + 0 comments ar[(ar[i]%10)-1] = ar[(ar[i]%10)-1]+10; specially this line

cha2168871 + 1 comment For anyone working with Java. If you are getting the error of n not found : int result = migratoryBirds(n, ar);

replace n with arCount, as it is a simple typo: int result = migratoryBirds(arCount, ar);

codeharrier + 0 comments C++ had the same issue.

antoniojsp + 0 comments Any opinion?

static int migratoryBirds(int n, int[] ar) { int count = 0; int maxCount = 0; int maxType = 0; for (int i = 1; i < 6; i++) { count = 0; for (int j = 0; j < n; j++) { if (ar[j] == i) { count++; } } if (count > maxCount) { maxCount = count; maxType = i; } } return maxType; }

poojaselvam18 + 2 comments what is the problem with my solution?

n=int(input()) ar=[int(x) for x in input().split()] countList=[] for i in ar: countList.append(ar.count(i)) max_c=max(countList) i=0 result=[] while i<len(countList): if countList[i]==max_c: result.append(ar[i]) i+=1 print(min(result))

karthiknathan + 0 comments :-):-):-)

abhishekvelankar + 0 comments result.append(i)

romyhermawan96 + 1 comment this is my algo in c# to solve the problem.

static int migratoryBirds(int n, int[] ar) { // Complete this function var dic = new Dictionary<int, int>(); dic.Add(1, 0); dic.Add(2, 0); dic.Add(3, 0); dic.Add(4, 0); dic.Add(5, 0); for (int i = 0; i < n; i++) { dic[ar[i]]++; } return dic.FirstOrDefault(Q => Q.Value == dic.Values.Max()).Key; }

iamacoolperson + 1 comment Can you explain what the last line is doing? My linq is pretty rusty. Specifically:

Q => Q.Value == dic.Values.Max()).Key

romyhermawan96 + 0 comments just to get the Key where value = max.

i think this code is better

var newArr = new int[n]; for (int i = 0; i < n; i++) { newArr[ar[i]]++; } var result = Array.IndexOf(newArr,newArr.Max()); return result;

Sort 753 Discussions, By:

Please Login in order to post a comment