*FINAL SOLUTION* : I gave a second thought :
A large amount of space(but finite constant and bounded and within practical limits) will eventually be required for my hashing based solution to be worst case O(n). So this problem has an linear time solution.. BUT can we do better in terms of space maintaining the time complexity? Well, I claim that we cannot ! :( Can anyone disprove/prove that we can do better ?? I don't think the 2 solutions above work -------------------------------------------------- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Thu, Apr 15, 2010 at 10:13 AM, Rohit Saraf <rohit.kumar.sa...@gmail.com>wrote: > the implementation of the hashmap in prev soln(to achieve constant time) is > non-trivial and is based on some exercise of Cormen. > > better and simple: > > Think of these points as nodes of the graph > use the UnionFind(quickunion) data structure... and everytime a union is > done add 1 to the component united. > find the one with count>500 > > > -------------------------------------------------- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14 > > > On Thu, Apr 15, 2010 at 9:16 AM, Rohit Saraf > <rohit.kumar.sa...@gmail.com>wrote: > >> I agree.... But that worst case will never come here. There are >> between 2 and 500 keys. And all keys are different.... So how would >> the worst case come?? >> >> On 4/14/10, gaurav kishan <gauravkis...@gmail.com> wrote: >> > This will be done in one pass i.e O(n). >> > On Wed, Apr 14, 2010 at 10:17 PM, gaurav kishan >> > <gauravkis...@gmail.com>wrote: >> > >> >> Can everyone check this out and let me the issues ? >> >> >> >> int[] i=new >> >> int[]{11,2,3,11,4,11,76,11,11,65,11,44,78,11,13,11,79,11,11,11,56}; >> >> int count=1,element=i[0]; >> >> for(int j=1;j<i.length;j++) >> >> { >> >> if(element==i[j]) >> >> count++; >> >> else >> >> { >> >> count--; >> >> if(count==0) >> >> { >> >> element=i[j]; >> >> count=1; >> >> } >> >> } >> >> >> >> } >> >> System.out.println("Mode is "+element); >> >> } >> >> >> >> Regards, >> >> Gaurav Kishan >> >> >> >> On Wed, Apr 14, 2010 at 10:01 PM, sharad kumar >> >> <aryansmit3...@gmail.com>wrote: >> >> >> >>> ya over here its >501 rite????? >> >>> >> >>> >> >>> On Wed, Apr 14, 2010 at 8:24 PM, Prakhar Jain <prakh...@gmail.com> >> wrote: >> >>> >> >>>> If m thinking right, >> >>>> That works if mode occurs >=n/2 times in the array >> >>>> >> >>>> Best, >> >>>> Prakhar Jain >> >>>> http://web.iiit.ac.in/~prakharjain/ >> >>>> >> >>>> >> >>>> On Wed, Apr 14, 2010 at 8:12 PM, sharad kumar < >> aryansmit3...@gmail.com >> >>>> > wrote: >> >>>> >> >>>>> can we make use of majority VOTE ALGORITHM? >> >>>>> >> >>>>> >> >>>>> 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> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@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> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@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> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@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> >> <algogeeks%2bunsubscr...@googlegroups.com<algogeeks%252bunsubscr...@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. >> > >> > >> >> -- >> Sent from my mobile device >> >> -------------------------------------------------- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14 >> > > -- 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.
