complexity : O(n) + O(nlogn)
Sweety wrote:
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
