@Saurabh: Again, this solution is not O(log(quotient)), but O(log(quotient)^2). Consider a = 15, b = 1. On the first call, the while loop increments k 4 times. On the first recursive call, k is incremented 3 times, then 2 times, and then 1 time. This is a total of 10 executions of the statement k++. Since loq_2(quotient) ~ 4, this is log_2(quotient) * (log_2(quotient) + 1) / 2 = O(log(quotient)^2).
Dave On Aug 27, 2:49 am, saurabh modi <saurabhmodi102...@gmail.com> wrote: > I think that this code can suffice. > > http://www.ideone.com/ESW8Z > > #include<stdio.h> > > int solve(int,int); > > int main() > { > printf("%d",solve(100,10)); > return 0; > > } > > int solve(int a,int b) > { > int quotient=0,k=0; > if(a<b) > return quotient; > while((1<<k)*b<=a) > { > k++; > } > k--; > quotient=(1<<k)+solve(a-(1<<k)*b,b); > return quotient; > > } > > It also gives correct answer.Plus,its easy to read and concise.it is > O(log(quotient)) solution. -- 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.
