# Divide two integers

**Problem statement**

Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT.

**Solution**

Obviously the naive approach to this problem would be to subtract the divisor from the dividend until the dividend becomes less than the divisor, while keeping track of how many times we subtracted.

This approach is not optimal. Imagine you would have to divide `2147483648`

by `1`

.

This problem can be solved based on the fact that any number can be converted to the format of the following:

So, we will increment our divisor by shifting it one position left at a time until it surpasses the divided. That is, multiply it by `2`

, by `4`

, by `8`

, etc. We then shift it one position to the right to get the maximum divisor that still fits in our divided and subtract that from our current dividend. We repeat the process for the rest of our dividend until it becomes smaller than our original divisor.

Example, let `dividend = 14 = 1110`

and `divisor = 1`

. We start by taking our divisor and shift it one position to the left, making it `divisor = 2`

. It still is less than or equal to `14`

. We continue by shifting it another position to the left, making it `divisor = 4`

, still less than `14`

. We do another shift and make it `divisor = 8`

, which is still less than `14`

. Finally, we shift it once more resulting in a `divisor = 16`

, which is greater than our `dividend = 14`

. Shifting it one position to the right will give us the largest divisor that fits into `14`

, which is `8`

and subtract that from our divided. We keep track of our multiplication factor and add it to our answer – three shifts to the left results in a factor of `8`

. Our answer becomes `8`

.

We continue with the rest of the dividend which is `14 - 8 = 6`

. Our divisor is larger than `6`

, so we shift it one position to the left making it `divisor = 2`

. We then shift it again making it `divisor = 4`

and finally another shift, resulting in a `divisor = 8`

, which is larger than `6`

. Shifting it one position to the right will give us the largest divisor that fits into `6`

, which is `4`

and subtract that from our divided.. We keep track of our multiplication factor and add it to our answer – two shifts to the left results in a factor of `4`

. Our answer becomes `12`

.

We continue with the rest of the dividend which is `6 - 4 = 2`

. Our divisor is larger than `2`

, so we shift it one position to the left making it `divisor = 2`

. We then shift it again making it `divisor = 4`

which is larger than `2`

. Shifting it one position to the right will give us the largest divisor that fits into `2`

, which is `2`

and subtract that from our divided. We keep track of our multiplication factor and add it to our answer – one shift to the left results in a factor of `2`

. Our answer becomes `14`

, which is also our final answer.

**Full code**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
class Solution(object): def divide(self, dividend, divisor): """ :type dividend: int :type divisor: int :rtype: int """ sign = 1 if (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0): sign = -1 dividend, divisor = abs(dividend), abs(divisor) ans = 0 while dividend >= divisor: tmp, d = 1, divisor while dividend >= d: d = d << 1 tmp = tmp << 1 d = d >> 1 tmp = tmp >> 1 dividend = dividend - d ans += tmp if sign < 0: ans = -ans return min(max(-2147483648, ans), 2147483647) def main(): solution = Solution() print(solution.divide(6, 2)) print(solution.divide(-1, 1)) print(solution.divide(-2147483648, -1)) if __name__ == "__main__": main() |