@Shashank : Nice solution :)
*Regards Sanju Happy to Help :)* On Fri, Aug 19, 2011 at 2:36 AM, WgpShashank <shashank7andr...@gmail.com>wrote: > We can use bit logic to reduce the time complexity to O(logn) where n is > Quotient > > Algorithm will be as follow as we know > > 1. Left shifting an unsigned number by 1 multiplies that number by 2. > 2. Right shifting an unsigned number by 1 divides that number by 2. > > Therefore the procedure for the division algorithm, given a dividend and a > divisor . > core logic will be to left shift (multiply by 2) untill its greater then > dividend , then continue this routine with the the difference between the > dividend and divisor and divisor till the point where dividend is less than > divisor or their difference is zero. > > Lets see one example: dividend=23 divisor=3 > > then left shift for 3 i.e 3 will converted to3, 6,12,24,… since 12 <23 > hence now dividend is 11 and quotient in 4(two time shift operation) now > again 3,6,12.. 6<11 hence dividend is 11-6=5 and quotient =4+2=6 now only > 3<5 hence remainder =2 quotient =6+1=7 so answer. > > Time Complexity O(logn) Number of bits in Quotient > > Correct me if anything wrong > > *Thanks > Shashank Mani > Computer Science > Birla Institute of Technology Mesra* > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/VszScC-sOfoJ. > > 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.
