I dont think so even if a solution which appears to be better than o(n) can actually be better.Because with this approach we are working upon each input test case rather than storing them somewhere and traversing it again.The only way this program can be improoved is in terms of memory i feel.
On Sun, Mar 27, 2011 at 4:41 PM, sukhmeet singh <[email protected]>wrote: > is there a better solution than O(n) ??? any datastructure possible > > On Wed, Mar 23, 2011 at 8:20 PM, .bashrc <[email protected]> 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 <[email protected]> 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 <[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. >> >> > -- > 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. > -- Saurabh Singh B.Tech (Computer Science) 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.
