Technical Interview

Tips, questions, answers and puzzles at
www.technical-interview.com

Thursday, April 29, 2010

Majority element

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.

Ans
Naive approach:

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.

Recursive Approach:

Here’s a divide-and-conquer algorithm:

function majority (A[1 . . . N])

if N = 1: return A[1]

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’’

else:

check whether either ML or MR is a majority element of A

if so, return that element; else return ‘‘no majority’’

No comments:

Post a Comment