algorithms kotlin

Problem 5.6 from EPI -> Compute X.div(Y)

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.

Leave a Reply

Your email address will not be published. Required fields are marked *