In my opinion also, this is a Majority vote algorithm as mentioned by Navin and as coded by Dave. Only point I would add to @Dave's code is that it wont be possible to find if the majority element has 2n/3 occurance as majority element keeps changing during the run and as the majority algorithm tells you a number which has greater than n/2 occurrence. So all you need to do is another liner scan after the majority element is found to check if its count is 2n/3.
@Narsimha Raju: your failure to find 2n/3 occurrence by adding a for loop is expected. Please reply if we are able to add a for loop into code above (given by @Dave) to find if majority element has 2n/3 occurance. Thanks, Sourav On Sep 22, 9:02 am, Navin Naidu <[email protected]> wrote: > Use majority vote algorithm: > > http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html > > > > On Wed, Sep 22, 2010 at 9:12 AM, pre <[email protected]> wrote: > > Hi all, > > pls help me solve this problem.. > > Design an algorithm to find the majority element of an array.. > > majority element must be an element tht has the cardinality greater > > than 2n/3 where n is the number of elements in the array and the time > > complexity must be a linear time.. ie o(n).. > > > hint : use mode or median to solve .. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]<algogeeks%[email protected]> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Thanks & Regards, > > - NMN -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
