A very frequent element An array A[1..n] is said to have a dominant element if m

Question

A very frequent element

An array A[1..n] is said to have a dominant element if more than half of the entries are the same. Given an array, the task is to design an efficient algorithm to tell whether the array has a dominant element, and, if so, find that element. The elements of the array are not necessarily from some ordered domain like the integers, and so there can be no comparisons of the form "is A[i] > A[j]?". (Think of the array elements as GIF files, say.) However, you can answer questions of the form "is A[i] = A[j]?" in constant time.

(a) Show how to solve the problem in O(n log n) time.

(b) Can you give a linear time algorithm?

Explanation / Answer

(a) This is done by divide and conquer. We divide the array A in to two parts A1 and A2. if x is the majority element in A then it must be the majority element in A1 or A2 or both. We find the majority elements in A1 and A2. If the both have same majority element then that is the answer. If one of them does not have a majority element then the other on is the answer. If both have a majority element, then we need to majority two lineat iterations of the array A and find out which one of them is the majority element.

T(n) = 2*T(n/2)+O(n) => T = O(nlogn)

(b) The idea is that if you count the number of majority elements and subtract number of the other elements frmo it. Then the result must be greater than zero. But if the result is zero then that number cannot be the majority element. This is a two step algorithm.

First step:

intialize maj=0 and count = 1

for i=0:i<size-1

if(A[maj]==A[i])

count++

else

count--

if(count==0)

maj=i;

count=1;

Second step:

Check if the number in A[maj] occurs more than n/2 times in the array. If it is then its the answer, if it does not then the array has no majority element.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.