I am trying to submit my solution but its giving TLE. My implemetation is
O(n).. and i am not able to think a faster algo than this for the problem.
The problem is based on finding the majority element concept. Please help
My code:
#include<iostream>
#include<string.h>
using namespace std;
struct res{
string boo;
int key;
};
long Majoritycount(int a[], int n)
{
int ctr=1;
int candidate = a[0];
int mindex=0;
for(int i=0;i<n;i++){
if(a[i]==a[mindex]) ctr++; //match - incr counter
else ctr--; //mismatch - dec counter
if(ctr==0) {
ctr=1;
mindex=i;
candidate=a[i];
}
}
return candidate;
}
int main()
{
struct res result[100];
int t,n,count=0;
int tt,cnt=0;
cin>>t;
tt=t;
while(t>0)
{
cin>>n;
int *arr=new int[n];
for(int i=0;i<n;i++)
cin>>arr[i];
int a=Majoritycount(arr,n);
for(int i=0;i<n;i++)
if(arr[i]==a)
count++;
if(count>(n/2))
{
result[t].boo="YES";
result[t].key=a;
}
else
{
result[t].boo="NO";
result[t].key=9999;
}
t--;
count=0;
}
for(int i=tt;i>0;i--)
{
if(result[i].key!=9999)
cout<<result[i].boo<<" "<<result[i].key<<"\n";
else
cout<<result[i].boo<<"\n";
}
return 0;
}
--
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.
