zatinmohan / moore-voting

Moore Voting Algorithm

Moore-Voting

Q- Array is given to you. You have to find that element that occurs more then size/2 times.

example --> 3 2 1 1 1 3 3 3 3
Answer - 3
Here size of array is 9 and 9/2 is 4. Here 3 occurs more than 4 times.

Working

• As the algorithm include a word VOTING in it's name so it is simply related to voting.
• In this Algorithm the first element has a count(vote) = 1.
• If There are similar people (elements) with similar agenda than the counter(vote) will increment by 1.
• If not then counter(vote) will be decremented by 1.
• If counter(vote) becomes 0 then
  • counter(vote) value becomes 1.
  • now comparision will be started from the point where the counter(vote) value becomes 0.
    
  • [To understand this point read the program and solve it on paper.]

COMPLEXITY

• Moore Voting - n
• Brute Force - n^2.