Moores Majority Voting Algorithm

Intuition Behind Working : When the elements are the same as the candidate element, votes are incremented whereas when some other element is found (not equal to the candidate element), we decreased the count. This actually means that we are decreasing the priority of winning ability of the selected candidate, since we know that if the candidate is in majority it occurs more than N/2 times and the remaining elements are less than N/2. We keep decreasing the votes since we found some different element(s) than the candidate element. When votes become 0, this actually means that there are the equal number of votes for different elements, which should not be the case for the element to be the majority element. So the candidate element cannot be the majority and hence we choose the present element as the candidate and continue the same till all the elements get finished. The final candidate would be our majority element. We check using the 2nd traversal to see whether its count is greater than N/2. If it is true, we consider it as the majority element.

Steps to implement the algorithm : Step 1 – Find a candidate with the majority –

Initialize a variable say i ,votes = 0, candidate =-1 Traverse through the array using for loop If votes = 0, choose the candidate = arr[i] , make votes=1. else if the current element is the same as the candidate increment votes else decrement votes. Step 2 – Check if the candidate has more than N/2 votes –

Initialize a variable count =0 and increment count if it is the same as the candidate. If the count is >N/2, return the candidate. else return -1.

dry_run

Dry run for the above example: Given : arr[]= 1 1 1 1 2 3 5 votes =0 1 2 3 4 3 2 1 candidate = -1 1 1 1 1 1 1 1 candidate = 1 after first traversal 1 1 1 1 2 3 5 count =0 1 2 3 4 4 4 4 candidate = 1
Hence count > 7/2 =3 So 1 is the majority element.

Code

def findMajority(arr, n):
 
    candidate = -1
 
    votes = 0
 
     
 
    # Finding majority candidate
 
    for i in range (n):
 
        if (votes == 0):
 
            candidate = arr[i]
 
            votes = 1
 
        else:
 
            if (arr[i] == candidate):
 
                votes += 1
 
            else:
 
                votes -= 1
 
    count = 0
 
     
 
    # Checking if majority candidate occurs more than n/2
 
    # times
 
    for i in range (n):
 
        if (arr[i] == candidate):
 
            count += 1
 
             
 
    if (count > n // 2):
 
        return candidate
 
    else:
 
        return -1
 
# Driver Code 
 
 
arr = [ 1, 1, 1, 1, 2, 3, 4 ]
 
n = len(arr)
 
majority = findMajority(arr, n)
 
print(" The majority element is :" ,majority)
 
     
# This 

Notes

• gyan_pelo
• So the trick is we can store only one element at a time while iterating.
• Keep track of two things one is the candidate with maximum votes and how many votes he got. So two variables.
• Now when iterating if the votes are 0 then assign current element to candidate else, either increase or decrease the vote count, if current element is same as candidate then increase vote by 1 else decrease by 1.
• In tutorial you can give example of votes for favourite animal, like dog, cat.
• It is strange but simple logic.