Sources: leetcode 29

Rating: medium

Given two integers `dividend`

and `divisor`

, divide two integers without using multiplication, division, or modulus operators. Return the quotient. Note that integer division truncates, and that 32-bit integers have maximum and minimum values.

def divide(dividend: int, divisor: int) -> int: # return the quotient without using multiplication, division, or modulus

**Solution**

First, check if the output quotient would be **negative** to simplify the later math.

def divide(dividend, divisor): negative = (dividend < 0) != (divisor < 0) divisor, dividend = abs(divisor), abs(dividend) # return the quotient

Since multiplication and division operators are forbidden, addition and subtraction will have to be used instead. To that end, start with a **quotient** value and a **count** value that will be used to build up to the final result while **dividend** is subtracted down using **divisor**.

def divide(dividend, divisor): negative = (dividend < 0) != (divisor < 0) divisor, dividend = abs(divisor), abs(dividend) quotient = 0 count = 1 # calculate the quotient using count return quotient

The reason **count** is used is because a linear approach of simply adding up divisor values would be too slow. Using **count** allows skipping up in multiples instead of iterating one by one. However, this creates the possibility of skipping too far, in which case the original **divisor** value should be remembered for resets.

def divide(dividend, divisor): negative = (dividend < 0) != (divisor < 0) divisor, dividend = abs(divisor), abs(dividend) quotient = 0 count = 1 div = divisor while div <= dividend: dividend -= div quotient += count count += count div += div # ensure dividend and divisor do not cross one another return quotient

This creates the possibility of **div** and **dividend** crossing one another, in which case the last step needs to be reverted back down by resetting the **div** and **count** values.

def divide(dividend, divisor): negative = (dividend < 0) != (divisor < 0) divisor, dividend = abs(divisor), abs(dividend) quotient = 0 count = 1 div = divisor while div <= dividend: dividend -= div quotient += count count += count div += div if dividend < div: div = divisor count = 1 return quotient

However, as 32 bit integers are limited in value, the returned **quotient** must be bound in value.

**Final Code**

def divide(dividend, divisor): negative = (dividend < 0) != (divisor < 0) divisor, dividend = abs(divisor), abs(dividend) quotient = 0 count = 1 div = divisor while div <= dividend: dividend -= div quotient += count count += count div += div if dividend < div: div = divisor count = 1 if negative: return max(-2147483648, -quotient) else: return min(quotient, 2147483647)