I feel gaurav's solution does it in O(n) time & cons space.... but there is a case that when there is no element with n/2+1 appearances the method might fail(eg 1 1 1 2 3 4 and in many other cases as well...) but as the problem states that there is atleast 1 element with n/2+1 appearances....this algo provides the answer to above question.
On Apr 15, 1:09 pm, Rohit Saraf <rohit.kumar.sa...@gmail.com> wrote: > *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 Bombayhttp://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...@googleg > >> roups.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...@googleg > >> roups.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...@googleg > >> roups.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...@googleg > >> roups.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.
