Question :Let A[1..n] be an array of integers. Design an efficient
divide and conquer algorithm to determine if A contains a majority
element, i.e an element appears more than n/2 times in A. What is the
time complexity of your algorithm?
Answer:
a[1..n] is an array
int majorityElement(int a[], int first, int last)
{
If (first = = last)
{
return a[first]; // Array has one element and its count = 1
and it is major element
}
mid= (first+last)/2;
(majorL,countL)= majorityElement(a,first,mid);
(majorR,countR)= majorityElement(a,mid
+1,last);
n = total elements in an array;
If(majorL==majorR)
return(countL+countR);
else
{
If(countL>countR)
return(majorL,countL);
elseif(countL< countR)
return(majorR,countR);
else
return(majorL,majorR);
}
if(countL>n/2)
temp1=majorL;
if(countR>n/2)
temp2=majorR;
If(temp1 = = temp2)
return temp1;
elseif(countL>countR)
return temp1;
else (countR>countL)
return temp2;
else
return -1;
}
int main()
{
int a[8] = {2,3,2,2,4,2,2,2};
int first =1;
int last=8; //change the value of last when the array
increases or decreases in size
int x = majorityElement(a,first,last);
if(x= = -1)
printf(“No Majority Element”)
else
Majority element = x;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
