CODEWITHSUNDEEP
c++algorithm
user2768684
user2768684

Reputation:

time majority vote algorithm error

here is the algorithm http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html and this is my code 

#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int ans,counter=0,a,temp=0,time=0;
    while(temp<n){
        cin>>a;
        if(counter==0)
        {
            counter=1;
            ans=a;
        }
        else if(counter>0){
            if(ans==a)
                ++counter;
            else
                --counter;
        }
        ++temp;
    }
    cout<<"The number "<<ans<<" is in the more majority ";
}

and my problem is when you give 6 6 1 2 3 it say that 3 is in the more majority

where is my problem? thanks

Upvotes: 0

Views: 247

Answers (2)

AShelly
AShelly

Reputation: 35540

I think you got the expected answer for the given data. The key is this quote from the linked page:

"When we are done, the current candidate is the majority element, if there is a majority."

In this case, there is no majority, so the algorithm returns an invalid result. Try again with input 6 6 6 1 2

Here's an implementation with no arrays that a professor is unlikely to accept:

#include <iostream>
using namespace std;
int majority(int n,int &ans,int counter){
  int a,i;
  if (!n) return 0;
  cin>>a;
  if (!counter) ans=a;
  counter+=2*(ans==a)-1;
  i=majority(n-1,ans,counter);
  return i+(ans==a);
}
int main(){
  int n,ans;
    cin>>n;
     if (n/2 < majority(n,ans,0))
        cout<<"The number "<<ans<<" is in the more majority "<<endl;
     else 
        cout<<"No majority"<<endl;
}

Upvotes: 1

LeartS
LeartS

Reputation: 2896

You correctly implemented the algorithm, but you didn't interpret it correctly.

The algorithm assumes there is a majority element (more than half the elements are that particular element) and returns it. If the assumption is false, you have to go through the entire sequence two times to check if there really is a majority.

In your example there is no majority and therefore the algorithm doesn't work.

Upvotes: 2

Related Questions