Let A be the input array;
Now algorithm is follows;
struct leave{
int cand;
int count;
};
struct leave tree[1200000];
void build(int s,int e,int node ,int *A)
{
if(s == e){
tree[node].cand = A[s];
tree[node].count = 1;
return;
}
else{
int mid = (s+e)>>1;
build(s,mid,2*node,A);
build(mid+1,e,2*node+1,A);
if(tree[2*node].cand == tree[2*node+1].cand){
tree[node].cand = tree[2*node].cand;
tree[node].count = tree[2*node].count +
tree[2*node+1].count;
}
else{
if(tree[2*node].count > tree[2*node+1].count){
tree[node].cand = tree[2*node].cand;
tree[node].count = tree[2*node].count -
tree[2*node+1].count;
}
else{
tree[node].cand = tree[2*node+1].cand;
tree[node].count = tree[2*node+1].count -
tree[2*node].count;
}
}
}
}
int main()
{
//read Array A
build(1,n,1);
//sort array A
int val = Tree[1].cand;
//perform binary search on sorted array A
//if its count is strictly greater than n/2 then yes else no
On Apr 15, 12:28 am, LALIT SHARMA <[email protected]> wrote:
> 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
> > [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.
