In this article, we will explore a Python algorithm for integer division, implemented without using built-in division, multiplication or modulo functions. The original problem statement can be found at LeetCode website, and here we will explore an efficient recursive solution to this problem.
Problem
Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod
operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero, which means losing its fractional part. For example,
truncate(8.345) = 8 and truncate(-2.7335) = -2.
Full Problem Statement
Solution
One basic approach would be to simply add divisor to an accumulator until the accumulator value becomes larger than divident. Then, the quotient would be the number of times that the divisor was added. The problem with that approach is in its performance. It is slow and inefficient for large dividends and small divisors.
A more efficient approach, and the one we are describing here, is to use bitwise operations on integers to calculate the quotient.
Operation 1 shifts the binary representation of the value stored in variable x to the left, for 1 bit. This has
the same effect as multiplication by 2 in decimal representation of x.
Operation 2 is the complementary operation of operation 1. It shifts x for 1 bit to the right. That has the same
effect as division by 2.
How can we use these two bitwise operations to calculate the quotient? Essentially, we are going to use a recursive function which will in each run start with quotient = 1 and and an accumulator variable initialized to the value of divisor. Then, we will use bitwise operator << to multiply both the quotient and accumulator by 2.
The initial value of accumulator can be also written as:
$$ \boldsymbol{accumulator} = \boldsymbol{divisor} * \boldsymbol{quotient} $$
That's true because the quotient is initialized to 1. Then, at each step in the loop, when we multiply accumulator by 2, we can see that as performing:
$$ \boldsymbol{accumulator} = \boldsymbol{divisor} * ( \boldsymbol{quotient} * 2 ) $$
In order to keep the quotient variable in sync with the accumulator, we also multiply it by 2 at every step, so we can keep track of its value all the time.
We will keep mutliplying by 2 until the accumulator value becomes larger than the dividend. Once that happens, we will return one step back, and use bitwise operator >> to obtain the largest quotient value which, when multiplied by divisor, is still less than dividend.
Example, if divident is 25 and divisor is 4, the procedure would generate these values:
Obviously, 32 is larger than 25, so we need to go one step back, from step 4 to step 3 and mark 4 as the correct value.
Once such a quotient value is found, it becomes a part of the return value for our recursive function. However, now when this value is calculated, we also need to resolve the difference between the dividend and accumulator (in our example, we need to handle a new dividend of 25 - 16, with divisor 4).
In order to do that, we need to call the recursive function with dividend parameter (current_dividend parameter) set to the value of: dividend � accumulator. That next recursive call will have a smaller dividend value and it will execute faster than the the original call. The parameter current_divisor is always set to the value of divisor supplied by the main program. This sameprocedure of recursive calls needs to continue until the current_dividend becomes equal or less than divisor (current_divisor). Once that happens, our recursive function hits the base case, and returns either 0 or 1; 0 if the current_dividend is less than divisor, and 1 if it is equal.
Note that the recursive function works only with positive values. That's why we will take care of potential negative sign outside of the recursive function, and call the recursive function with absolute values of initial dividend and divisor.
Time and Space Complexity
Since we have a total of b recursive calls, and each recursive call is O(logN), where N is the dividend input,
the final time complexity is O(b logN).
Space complexity is just O(b), since every recursive call is O(1).
Source code
Code:
class Solution:
MIN_INT = pow(-2, 31)
MAX_INT = pow(2, 31) - 1
def recursive_divide(self, current_dividend: int, current_divisor: int):
quotient = 1
accumulator = current_divisor # same as current_divisor * quotient because quotient == 1 at this point
# base case
if current_dividend < current_divisor:
return 0
elif current_dividend == current_divisor:
return 1
while accumulator < current_dividend:
quotient = quotient << 1
accumulator = accumulator << 1 # implicit quotient inclusion here!
# undo the last step, because accumulator is now larger than current_dividend
accumulator = accumulator >> 1
quotient = quotient >> 1
return quotient + self.recursive_divide(current_dividend - accumulator, current_divisor)
def divide(self, dividend: int, divisor: int) -> int:
'''
Main method of this module.
:param dividend:
:param divisor:
:return:
'''
# determine the sign of quotient:
negative = False
if (dividend >= 0 and divisor >= 0):
negative = False
elif (dividend < 0 and divisor >= 0):
negative = True
elif (dividend > 0 and divisor <= 0):
negative = True
# extract positive values of dividend and divisor:
abs_dividend, abs_divisor = abs(dividend), abs(divisor)
# watch for limits:
if (abs_divisor == 1):
if (negative == True):
return -abs_dividend if Solution.MIN_INT < -abs_dividend else Solution.MIN_INT
else:
return abs_dividend if Solution.MAX_INT > abs_dividend else Solution.MAX_INT
q = self.recursive_divide(abs_dividend, abs_divisor)
return q if negative == False else -q