We are given an array and we want to find its majority element, if it has one, using a divide-and-conquer algorithm in O(n*log.n).

A majority element of an n-sized array is defined as an element that appears more than n/2 times.

Solution

We will keep dividing the array into half until we reach an array of size two and we will compare the two elements of each array. If they are the same, they are the majority element of that array and we will return their value. If they are not the same, we will return a special character to signify that there is no majority element.

Moving recursively up the arrays, we will check the values we get from the two child-arrays/halves. As with the base case above, if the elements are the same, we return them, otherwise we return the special character.

Essentially we are checking two elements each time and if they are the same we keep them, while otherwise we discard them.

This is a simple example of a “Divide and Conquer” algorithm which showcases how to use the particular technique to our advantage. We have a big problem which will be easier to solve if we break it up into smaller problems. We keep breaking the problem up until we get to a base case (here the 2-element array) which we can trivially solve and then recursively propagate the solution up until we solve the original problem.

You can find the code here.

NOTE: This particular problem also has an O(n) solution without the use of divide-and-conquer. Can you find it?

Advertisements

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