Yes , I also need the same...Thanks for the help . On Fri, Apr 15, 2011 at 12:52 AM, vishwakarma <[email protected]>wrote:
> 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. > > -- Lalit Kishore Sharma, IIIT Allahabad (Amethi Capmus), 6th Sem. -- 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.
