Moore’s Voting Algorithm

So today I learnt about the Moore’s voting algorithm to find the majority element in a given array.

So what does Majority Element means →

So basically if any number in a element appears more than n/2 times the length of the array. That element is considered to be the majority element.

So suppose we have a array

A = [1, 3 , 3 ,5 ,3, 5, 3, 1, 3]

So if we count the frequency of each element in this array

1 → appears 2 times

3 → appears 5 times (Maj)

5 → appears 2 times

So accordingly our majority element will be = 3 , since

Length of the array = 9

Majority criteria = 9/2 = 4.5

So 3 is more than 4.5 , hence 3 is the majority element for this array.

Also point to be noted is If we substract the frequency of non-majority numbers with the frequency of majority number…

Freq of 3 (5) – ( freq. of 1(2) + Freq of 5(2) )

5-2+2 = 1 ( always gives a non-zero integer).

Ultimately that means that if the number is majority the difference will always be greater than 0.

So this makes the assumption for Moore’s algo that..

If we initialise a counter to 1 and take the first index element of the array as the majority index..

If we start comparing my current majority element with the next element..

If the next element is equal to my current majority element then, I will increase the counter to 1, else I will decrease the counter by 1.

If the counter hits 0 for a particular element..that particular element is now made the new majority element. And the counter is reinitialized back to 1.

Until all the elements are crawled in the array..we do the process to find our candidate element..

Once we find the candidate element.. we need to verify it to make sure it satisfies our condition for majority element which is – it should be greater than ( len of arr)/2. It makes sure that our candidate is good for majority or not and then if verification is success..

We print out the element. Else no majority element found.

This algorithm solves the problem to find the majority element in O(n) time complexity.. since it doesnt involve any type of sorting or nested loops..

# Program to find the majority element in an array
# Driver code
A = [1, 3 , 3 ,5 ,3, 5, 3, 1, 3]
def findCandidate(A):
  # Find the candidate for majority element
  candidate = A[0]
  count = 1
  for i in range(1, len(A)):
    if A[i] == candidate:
      count += 1
    else:
      count -= 1
    if count == 0:
      candidate = A[i]
      count = 1
  # return the candidate
  return candidate
def isMajority(A, cand):
  # Find the count of the candidate
  count = 0
  for i in range(len(A)):
    if A[i] == cand:
      count += 1
  if count > len(A)/2:
    return True
  else:
    return False
def printMajority(A):
  # Print the candidate if it is majority
  cand = findCandidate(A)
  if isMajority(A, cand) == True:
    print("Majority Element is: ", cand)
  else:
    print("Majority Element is not present")
    
printMajority(A)
# Majority Element is: 3