i m getting TLE for this soln and m not getting the concept used in
the above soln can anyone help??
#include<iostream>
using namespace std;
int main()
{
int t,n,k,no,flag;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
k = n;
int a[1000000] = {0};
flag = 0;
while(k--)
{
scanf("%d",&no);
a[no + 1000]++;
if(a[no + 1000] > n/2)
{
printf("YES %d\n",no);
flag = 1;
break;
}
}
if(flag == 0)
printf("NO\n");
}
return 0;
}
On Mar 16, 12:13 am, UTKARSH SRIVASTAV <[email protected]>
wrote:
> tahnks balaji i have got ac in this problem ........my prog is same only in
> the end i have taken a loop and
> @ akshata the link for the prob ishttps://www.spoj.pl/problems/MAJOR/
> MY CODE IS
> #include<stdio.h>
> main()
> {
> long long int n,t,r[1000000],count,major,i;
> scanf("%lld",&t);
> while(t--)
> {
> scanf("%lld",&n);
> scanf("%lld",&r[0]);
> major=r[0];
> count=1;
> for(i=1;i<n;i++)
> {
> scanf("%lld",&r[i]);
> if(r[i]!=major)
> {
> count--;
> if(count<0)
> { count=1;
> major=r[i];
> }
> }
> else
> {
> count++;
> }
> }
> /*if(count<=0)
> printf("NO\n");
> else
> printf("YES%lld\n",major);*/
> count=0;
> for(i=0;i<n;i++)
> {
> if(r[i]==major)
> count++;
> }
> if(count>n/2)
> printf("YES %lld\n",major);
> else
> printf("NO\n");}
>
> scanf("%lld",&r[0]);
> return 0;
>
> }
>
> On Tue, Mar 15, 2011 at 10:34 AM, Balaji Ramani
> <[email protected]>wrote:
>
>
>
>
>
>
>
>
>
> >http://www.spoj.pl/problems/MAJOR/
>
> > <http://www.spoj.pl/problems/MAJOR/>Thanks,
> > Balaji.
>
> > On Tue, Mar 15, 2011 at 11:00 PM, Akshata Sharma <
> > [email protected]> wrote:
>
> >> hey link to the problem??
>
> >> On Tue, Mar 15, 2011 at 10:50 PM, Balaji Ramani <
> >> [email protected]> wrote:
>
> >>> It fails for input 1,2,3. I think there needs to be one more iteration to
> >>> check if the candidate is actually a majority element or not.
>
> >>> Thanks,
> >>> Balaji.
>
> >>> On Tue, Mar 15, 2011 at 9:50 PM, UTKARSH SRIVASTAV <
> >>> [email protected]> wrote:
>
> >>>> CAN ANYONE PLEASE TELL ME WHY MY CODE IS GIVING WRONG ANSWER OR SOMEONE
> >>>> WHO HAS GOT AC IN THIS PROBLEM MAY POST HIS SOLUTION
>
> >>>> #include<stdio.h>
> >>>> main()
> >>>> {
> >>>> long long int n,t,r,count,major,i;
> >>>> scanf("%lld",&t);
> >>>> while(t--)
> >>>> {
> >>>> scanf("%lld",&n);
> >>>> scanf("%lld",&r);
> >>>> major=r;
> >>>> count=1;
> >>>> for(i=1;i<n;i++)
> >>>> {
> >>>> scanf("%lld",&r);
> >>>> if(r!=major)
> >>>> {
> >>>> count--;
> >>>> if(count<0)
> >>>> { count=1;
> >>>> major=r;
> >>>> }
> >>>> }
> >>>> else
> >>>> {
> >>>> count++;
> >>>> }
> >>>> }
> >>>> if(count<=0)
> >>>> printf("NO\n");
> >>>> else
> >>>> printf("YES%lld\n",major);
> >>>> }
> >>>> return 0;
> >>>> }
>
> >>>> --
> >>>> *UTKARSH SRIVATAV*
> >>>> *CSE-3
> >>>> B-Tech 2nd Year
> >>>> @MNNIT ALLAHABAD*
>
> >>>> --
> >>>> 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.
>
> >>> --
> >>> 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.
>
> >> --
> >> 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.
>
> > --
> > 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.
>
> --
> *UTKARSH SRIVATAV*
> *CSE-3
> B-Tech 2nd Year
> @MNNIT ALLAHABAD*
--
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.
