I can post solution of this complexity if you want !! On Apr 15, 12:19 am, vishwakarma <[email protected]> wrote: > 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 [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.
