Re: [algogeeks] Re: Need help on Divide and Conquer Algorithm
Solution:
int majorityElement(int a[], int n) {
if (a == null || a.length == 0 || n<=0) return -1;
int mElement = a[0];
int count=1;
for (int i=1; i < n; i++) {
if (a[i] == mElement) {
count++;
} else {
count--;
}
if (count <= 0) {
count = 1;
mElement = a[i];
}
}
count =0;
for (int i=0; i= n/2) ? mElement : -1;
}
On Thu, May 12, 2011 at 10:38 PM, pacific :-) wrote:
> a sort and another traversal would also do the same job in o( nlogn + n )
> ??
>
>
> On Fri, Apr 15, 2011 at 12:49 AM, vishwakarma > 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 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.
>>
>>
>
>
> --
> regards,
> chinna.
>
> --
> 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.
>
--
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.
Re: [algogeeks] Re: Need help on Divide and Conquer Algorithm
a sort and another traversal would also do the same job in o( nlogn + n )
??
On Fri, Apr 15, 2011 at 12:49 AM, vishwakarma
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 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.
>
>
--
regards,
chinna.
--
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.
[algogeeks] Re: Need help on Divide and Conquer Algorithm
example : let the array be { a,b,a,b,c,d,e,d,d,e,f};
now...
step 1 :pick any 2 different element and remove from the array till
array contains only same elements or any single element ...// dis
is implemented wid the above mentioned funtion " build() "
if there is any element whose occurence is greater than n/2 than u ll
always get an unique value left after step 1 , it wont depend on the
way u select 2 different element n removing them.
On Apr 15, 12:43 am, vishwakarma wrote:
> Let A be the input array;
>
> Now algorithm is follows;
>
> struct leave{
> int cand;
> int count;};
>
> struct leave tree[120];
>
> 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 wrote:
>
> > Yes , I also need the same...Thanks for the help .
>
> > On Fri, Apr 15, 2011 at 12:52 AM, vishwakarma
> > wrote:
>
> > > I can post solution of this complexity if you want !!
>
> > > On Apr 15, 12:19 am, vishwakarma 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
> > > emailtoalgoge...@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.
>
> > --
> > 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 algogee
[algogeeks] Re: Need help on Divide and Conquer Algorithm
Let A be the input array;
Now algorithm is follows;
struct leave{
int cand;
int count;
};
struct leave tree[120];
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 wrote:
> Yes , I also need the same...Thanks for the help .
>
> On Fri, Apr 15, 2011 at 12:52 AM, vishwakarma
> wrote:
>
>
>
> > I can post solution of this complexity if you want !!
>
> > On Apr 15, 12:19 am, vishwakarma 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
> > toalgoge...@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.
>
> --
> 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 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.
Re: [algogeeks] Re: Need help on Divide and Conquer Algorithm
Yes , I also need the same...Thanks for the help .
On Fri, Apr 15, 2011 at 12:52 AM, vishwakarma
wrote:
> I can post solution of this complexity if you want !!
>
> On Apr 15, 12:19 am, vishwakarma 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 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.
>
>
--
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 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.
[algogeeks] Re: Need help on Divide and Conquer Algorithm
I can post solution of this complexity if you want !!
On Apr 15, 12:19 am, vishwakarma 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 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.
[algogeeks] Re: Need help on Divide and Conquer Algorithm
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.
