Home > Applied Algorithms, Arrays, Iteration, Math > Find the element which occurs > n/2 times in an array with n elements

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_candidate and count (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 the current_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 the current_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! 🙂

Advertisements
  1. June 25, 2013 at 5:44 pm

    Keep blogging.Awesome Stuff 🙂

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: