link to problem: http://www.spoj.pl/problems/MAJOR/
On Feb 14, 5:03 pm, Akshata Sharma <akshatasharm...@gmail.com> wrote:
> 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.
