use prefix tree . so simply for each node declare an array of 10 elements within it.
On Tue, Aug 2, 2011 at 10:52 PM, Amol Sharma <amolsharm...@gmail.com> wrote: > i was solving the problem > > https://www.spoj.pl/problems/PHONELST/ > > and got TLE....somebody suggest some faster method > > #include<iostream> > #include<cstdio> > #include<vector> > #include<string> > #include<algorithm> > #include<cmath> > > using namespace std; > > int compare(int n1,int n2) > { > if(n1==n2) > return 1;//prefix is present print NO in this case > int s1=log10(n1); > int s2=log10(n2); > while(s1) > { > int t1=n1/pow(10.0,s1); > int t2=n2/pow(10.0,s2); > > if(t1==t2) > { > s1--;s2--; > } > else > { > return 0;//not a prefix....that is what we want > } > } > n2=n2/pow(10.0,s2); > //after while loop i am checking the last position of smaller number > and that position of the larger number > if( (n1%10)==(n2%10) ) > > return 1;//prefix is present print NO in this case > else > return 0; > } > > > int main() > { > int tc,flag; > scanf("%d",&tc); > while(tc--) > { > vector<int> v; > int n; > int temp; > scanf("%d",&n); > for(int i=0;i<n;i++) > { > scanf("%d",&temp); > v.push_back(temp); > } > sort(v.begin(),v.end()); > > vector<int>::iterator i,j; > int k,l; > for(i=v.begin(),k=0; k<n-1; k++,i++) > { > for(j=i,l=k+1;l<n;l++) > { > j++; > flag=compare(*i,*j); > if(flag==1) > { > printf("NO\n"); > break; > } > } > if(flag==1) > break; > } > if(flag==0) > printf("YES\n"); > } > return 0; > } > > > > > > -- > > > Amol Sharma > Third Year Student > Computer Science and Engineering > 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. > -- ........................ *MOHIT VERMA* -- 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.
