## Find the element which occurs > n/2 times in an array with n elements

Guess what? The Election Commissioner just called upon you to count the **10 billion votes** and find out the person who has majority votes! You are flabbergasted! You had a weekend of good sleep planned out with snack breaks every 2 hours and now you are stuck with this grunt work! **However,** **the EC ensures you that the one who wins will have more than half the total number of votes!**

If you think of **keeping a counter** for each of the (assume **(5 billion – 1) candidates**) and then go on to find the one with the maximum number of votes by incrementing counts, well you can forget the next 3000 weekends and say goodbye to your sleep.

And if you have the brilliant idea of **sorting the votes in some order** and getting the answer, you might just want to find one of those supercomputer’s access key.

What you should notice is that more than half the votes are for the winner. This can be solved using **Moore’s Voting algorithm in O(n) time with constant space**. Here is what you do.

1. Take two variables,current_candidateandcount(which corresponds to count of current candidate)

2. Set count to 0 initially.

3. Now everytime you find the count to be 0 (even at the beginning), make the current element as thecurrent_candidate.

4. Move forward in the array. If you find element the same as current candidate, increment count. If not, decrement count.

5. If count is 0, go to step 3. Else, move forward in the array

6. After traversing the whole array you’ll be left with the majority vote as thecurrent_candidate.

Bam! Want an example?

**B B C G H B B B T**

*Start with* candidate = (none), count = 0

First is a B, candidate = B, count = 1

moving forward, another B, candidate = B, count = 2

now a C, candidate = B, count = 1

and a G, candidate = (none), count = 0

now an H, candidate = H, count = 1

now a B, candidate = (none), count = 0

and another B, candidate = B, count = 1

and one more B, candidate = B, count = 2

and finally T,** candidate = B**, count = 1

Hence, you arrive on the answer candidate –> B !

Weekend plans to sleep might still pan out, eh? Cheers! 🙂

Keep blogging.Awesome Stuff 🙂