Using recursion we can do in O(1) space complexity and O(n) time
complexity..
int multiply(int a[], int n, int prevproduct, int i)
{
int nextproduct = 1;
if(i>=n)
return 1;
nextproduct = multiply(a, n, prevproduct*a[i], i+1);
printf("i=%d product=%d \n ", i, prevproduct*nextproduct);
nextproduct *= a[i];
return nextproduct;
}
int main()
{
int a[] = {1,2,3,4,5};
multiply(a,5,1,0);
getchar();
return 0;
}
On Mon, Jul 18, 2011 at 6:15 AM, Dumanshu <duman...@gmail.com> wrote:
> @Hary: thanks, ur code works. Could someone tell me the complexity of
> the above mentioned code???
> heres the working version of the same http://ideone.com/fDTfj
> Its increasing exponentially.. so can we say log_2(n)???
>
> On Jul 18, 1:57 am, Dumanshu <duman...@gmail.com> wrote:
> > are u sure that this code works??? because last time i checked it
> > didn't.
> >
> > On Jul 18, 1:22 am, hary rathor <harry.rat...@gmail.com> wrote:
> >
> > ary:
> >
> >
> >
> >
> >
> > > int dividend,divisor,remainder;
> > > int division(int p,int q){
> > > int quotient=1;
> > > /*if divisor and diviend are equal then quotient=1*/
> > > if(p==q){
> > > remainder=0;
> > > return 1;}
> >
> > > /*if dividend is smaller than divisor then remainder=dividend*/
> > > if(p<q){
> > > remainder=p;
> > > return 0;}
> >
> > > /*shift left till divisor > dividend*/
> > > while(p>=q){
> > > q<<=1;
> > > quotient<<=1;}
> >
> > > /*shift right for one time so that divisor become smaller than
> dividend*/
> > > q>>=1;
> > > quotient>>=1;
> > > /*again call division recurcively*/
> > > quotient+=division(p-q,divisor);
> > > return quotient;
> >
> > > }
> >
> > > int * demo()
> > > {
> > > int i;
> > > long long long long long int multi=1;
> > > for(i=0;i<a.len;i++)
> > > {
> > > multi*=a[i];
> >
> > > }
> >
> > > for(i=0;i<a.len;i++)
> > > {
> > > out[i]=mul[i]/a[i];
> >
> > > }
> > > }- Hide quoted text -
> >
> > > - Show quoted text -
>
> --
> 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.
