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.
