A Linear-time Majority Vote Algorithm Problem: How to decide, in one pass which element of a sequence is in the majority, provided there is such an element.
As we sweep through the sequence, we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0. When we move the pointer forward over an element e: - If the counter is 0, we set the current candidate to e and we set the counter to 1. - If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate. When we are done, the current candidate is the majority element, if there is a majority. If you must confirm that the chosen element is indeed the majority element, you must take one more linear pass through the data to do it. if Counter is greater than 0 at the end then we get the majority element in candidate field. Now, just count the number of times it occurred in the list using one more traversal and if now this count is greater than n/2 then return true or false otherwise. So, total pass = 2n -> order is O(n) On Sun, Nov 7, 2010 at 11:15 AM, Ashim Kapoor <[email protected]> wrote: > Is'nt this solvable by the majority vote algorithm already discussed in > this list? > > Ashim. > > > On Sun, Nov 7, 2010 at 3:42 AM, lichenga2404 <[email protected]>wrote: > >> There are many secret groups in College A.Every student at college A >> is a member or these secret group, though membership in one excludes a >> student from joining any other group. You wish to determine if any one >> of these groups contains more than half of the student population. To >> achieve this , you will introduce 2 students to each other: if they >> are members of different group , they will smile. If different group , >> they will nod. How to determine if any one group has more than half of >> the student population as members in O(n) introductions . And justify >> the answer. >> >> -- >> 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. >> >> > -- > 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. > -- 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.
