Given an array of size N ,we need to find the majority element if it exists ,as efficiently as possible. A majority element in an array of size N is any element which is present more than N/2 times.
Just scan the array element wise and then make a count of the frequency of each of the distinct elements present in the array and if any element's count is more than N/2 then it is the majority element, otherwise it doesn't exist!!
One needn't ponder much on the complexity of this bruteforce approach.
This requires O(N) additional space and O(N) time.
Here’s a divide-and-conquer algorithm:
function majority (A[1 . . . N])
if N = 1: return A
let AL , AR be the first and second halves of A
ML = majority(AL ) and MR = majority(AR )
if neither half has a majority:
return ‘‘no majority’’
check whether either ML or MR is a majority element of A
if so, return that element; else return ‘‘no majority’’