Compute a quotient given x and y without using division. The brute force solution would be to keep deducting y from x until x is less then y, but as always there is a better way. Reverse the operation, make it a multiplication operation, first find out which power of 2 times y is less or equal to x, then deduct that from x, while adding that power of two to the result. Running complexity is 0(n), take a look at the code here.
Categories