[algogeeks] Need help on Divide and Conquer Algorithm

[Sweety]

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.