# Divide Two Integers

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)
```