is there a better solution than O(n) ??? any datastructure possible
On Wed, Mar 23, 2011 at 8:20 PM, .bashrc <saurab...@gmail.com> wrote:
> I may be wrong but if no==1000 then it becomes a[1000000] which is
> beyond your array limit....
>
> On Mar 18, 12:31 am, KK <kunalkapadi...@gmail.com> wrote:
> > 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 <usrivastav...@gmail.com>
> > 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
> > > <rbalaji.psgt...@gmail.com>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 <
> > > > akshatasharm...@gmail.com> wrote:
> >
> > > >> hey link to the problem??
> >
> > > >> On Tue, Mar 15, 2011 at 10:50 PM, Balaji Ramani <
> > > >> rbalaji.psgt...@gmail.com> 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 <
> > > >>> usrivastav...@gmail.com> 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 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.
> >
> > > >> --
> > > >> 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.
> >
> > > --
> > > *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 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.
