# LeetCode 29. Divide Two Integers

## Description

https://leetcode.com/problems/divide-two-integers/

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

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: `[−231, 231 − 1]`. For this problem, assume that your function returns `231 − 1` when the division result overflows.

Example 1:

```Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.
```

Example 2:

```Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.
```

Example 3:

```Input: dividend = 0, divisor = 1
Output: 0
```

Example 4:

```Input: dividend = 1, divisor = 1
Output: 1
```

Constraints:

• `-231 <= dividend, divisor <= 231 - 1`
• `divisor != 0`

## Explanation

Keep multiplying divisor by 2, until it is just smaller than the dividend. At the same, count how many times we multiply the divisor by 2.

## Python Solution

``````class Solution:
def divide(self, dividend: int, divisor: int) -> int:
print (1 << 1)
is_negative = False

if dividend > 0  and divisor < 0 or dividend < 0 and divisor > 0:
is_negative = True

if dividend < 0:
dividend = -dividend

if divisor < 0:
divisor = -divisor

result = 0

while dividend >= divisor:
temp = divisor

count = 1

while dividend >= temp:
dividend -= temp
result += count

count <<= 1
temp <<= 1

if is_negative:
result = -result

if result >= 1 << 31:
result = (1 << 31) - 1

return result``````
• Time Complexity: O(N).
• Space Complexity: O(1).