Plz correct me if i am wrong On Sun, Mar 27, 2011 at 4:50 PM, saurabh singh <[email protected]> wrote:
> 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 > > > -- 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.
