check this http://www.geeksforgeeks.org/archives/7527
time O(n) space O(n) -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad <http://gplus.to/amolsharma99> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://youtube.com/amolsharma99> On Fri, Sep 30, 2011 at 1:40 AM, raju <[email protected]> wrote: > @ karthikeyan .. you're using O(n) space .. > > Try do it in O(n) time with O(1) space ... > Array sorted or not doesn't matter !!! > > ~raju > > > On Thu, Sep 29, 2011 at 9:20 PM, KARTHIKEYAN V.B. <[email protected]>wrote: > >> >> //use dynamic programming approach >> >> //it is O(n) time and O(1) space >> >> #include<stdio.h> >> #define N 5 >> >> void main() >> { >> int a[N]={1,2,3,4,5},i; >> int prod1[N]; >> int p=1; >> for(i=0;i<N;++i) >> { >> prod1[i]=p; >> p*=a[i]; >> } >> >> int prod2[N]; >> p=1; >> for(i=N-1;i>=0;--i) >> { >> prod2[i]=p; >> p*=a[i]; >> } >> >> int products[N]; >> for(i=0;i<N;++i) >> { >> products[i]=prod1[i]*prod2[i]; >> printf("%d ",products[i]); >> } >> } >> >> -- >> 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.
