O(n) is indeed the lower bound of any algorithm on this problem :) Yes. O(nlogn) is trivial.
Sort the given array. And count the number of occurrences of each element. For some element u ll get it as 501. U have found that element! And about the hashmap based solution. Hashmap internally uses a tree based structure. So, your 'n' insertion operations will indeed take O(n*logn) time. I guess you meant using "Hashing technique". i,e Using a hash function to add elements to the bucket array. And then check all the buckets with more than 500 elements [ since there can be collisions ]. And in one of them there will be 501 same elements. This soln is going to take O(1) expected time. The open question is to look for an algorithm to find the mode in O(n) worst case time complexity. On Wed, Apr 14, 2010 at 6:33 PM, Rohit Saraf <rohit.kumar.sa...@gmail.com>wrote: > O(n log n) will be trivial. > > O(n) is required at any cost. (Consider the case with 501 "1"s and 499 > "0"'s) > > Ok, so u can make a hashmap with your integer as keys and frequency as the > value. > No of keys will be between 2 and 500. (=> Traversing through takes > O(n) ) > You will have to traverse the array exactly once => O(n) > => O(n) solution. > > And it cannot be made better ! > > -------------------------------------------------- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > > > On Wed, Apr 14, 2010 at 4:14 PM, Gauri <gauri...@gmail.com> wrote: > >> Say If I have an array of 1,000 32-bit integers .And one of the value >> is occuring 501 number of times or more in the array. Can someone help >> me devise an efficient algorithm for the same ? >> >> Thanks & Regards >> Gauri >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Thanks and regards Rizwan A Hudda http://sites.google.com/site/rizwanhudda -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
