# LeetCode 29: Divide Two Integers

## Problem Restatement

We are given two integers, `dividend` and `divisor`.

We need to compute the integer quotient of:

```python
dividend / divisor
```

But we cannot use multiplication, division, or modulo operators.

The result should truncate toward zero. That means we remove the fractional part.

Examples:

```python
10 / 3 = 3.333...  -> 3
7 / -3 = -2.333... -> -2
```

The answer must stay inside the 32-bit signed integer range:

```python
[-2^31, 2^31 - 1]
```

If the answer is larger than `2^31 - 1`, return `2^31 - 1`.

The divisor is never zero. The statement gives `-2^31 <= dividend, divisor <= 2^31 - 1` and `divisor != 0`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two integers: `dividend` and `divisor` |
| Output | The integer quotient |
| Truncation | Toward zero |
| Forbidden operators | Multiplication, division, modulo |
| Integer range | 32-bit signed integer range |
| Special overflow case | `-2^31 / -1` returns `2^31 - 1` |

Function shape:

```python
def divide(dividend: int, divisor: int) -> int:
    ...
```

## Examples

Example 1:

```python
dividend = 10
divisor = 3
```

The exact value is:

```python
10 / 3 = 3.333...
```

After truncating toward zero:

```python
3
```

Return:

```python
3
```

Example 2:

```python
dividend = 7
divisor = -3
```

The exact value is:

```python
7 / -3 = -2.333...
```

After truncating toward zero:

```python
-2
```

Return:

```python
-2
```

Example 3:

```python
dividend = -2147483648
divisor = -1
```

The exact value is:

```python
2147483648
```

This is greater than the maximum 32-bit signed integer.

Return:

```python
2147483647
```

## First Thought: Repeated Subtraction

Division can be seen as repeated subtraction.

For example:

```python
10 / 3
```

means:

```python
10 - 3 = 7
7 - 3 = 4
4 - 3 = 1
```

We subtracted `3` exactly `3` times.

So the quotient is `3`.

A direct version would look like this:

```python
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        negative = (dividend < 0) != (divisor < 0)

        a = abs(dividend)
        b = abs(divisor)

        quotient = 0

        while a >= b:
            a -= b
            quotient += 1

        if negative:
            quotient = -quotient

        return quotient
```

This gives the right idea, but it is too slow.

## Problem With Repeated Subtraction

If `dividend` is very large and `divisor` is small, repeated subtraction needs too many loops.

For example:

```python
2147483647 / 1
```

The loop would subtract `1` more than two billion times.

That is not practical.

We need to subtract larger chunks.

## Key Insight

Instead of subtracting one `divisor` at a time, subtract doubled groups.

For example, to compute:

```python
43 / 3
```

The divisor can be doubled:

| Multiple count | Value |
|---|---|
| `1` | `3` |
| `2` | `6` |
| `4` | `12` |
| `8` | `24` |
| `16` | `48` |

The largest doubled value that fits inside `43` is `24`, which equals `8` copies of `3`.

Subtract it:

```python
43 - 24 = 19
```

Now repeat with `19`.

The largest doubled value that fits is `12`, which equals `4` copies.

```python
19 - 12 = 7
```

Now the largest doubled value that fits is `6`, which equals `2` copies.

```python
7 - 6 = 1
```

Now `1 < 3`, so we stop.

The quotient is:

```python
8 + 4 + 2 = 14
```

And:

```python
43 / 3 = 14 remainder 1
```

This avoids subtracting `3` fourteen times.

## Algorithm

First handle the overflow case:

```python
if dividend == -2**31 and divisor == -1:
    return 2**31 - 1
```

Then determine the sign of the answer.

The answer is negative when exactly one of `dividend` and `divisor` is negative.

```python
negative = (dividend < 0) != (divisor < 0)
```

Work with positive absolute values:

```python
a = abs(dividend)
b = abs(divisor)
```

Now compute how many times `b` fits into `a`.

While `a >= b`:

1. Start with one copy of `b`.
2. Keep doubling the current chunk while the doubled chunk still fits inside `a`.
3. Subtract the largest chunk from `a`.
4. Add the corresponding count to the quotient.

At the end, apply the sign.

## Correctness

The algorithm keeps a remaining value `a`.

At any point, the original absolute dividend equals:

```python
quotient * abs(divisor) + a
```

The algorithm repeatedly chooses a doubled chunk:

```python
abs(divisor), 2 * abs(divisor), 4 * abs(divisor), ...
```

Each chunk is a valid multiple of the divisor, and the chosen chunk never exceeds the current remaining value `a`.

When we subtract a chunk, we add its multiple count to `quotient`. Therefore, the invariant remains true.

The loop stops when:

```python
a < abs(divisor)
```

At that point, the remaining value is smaller than one more divisor, so no additional whole copy of the divisor can fit.

Thus `quotient` is exactly the integer quotient of the absolute values.

Finally, applying the sign gives truncation toward zero. The overflow case is handled before the main loop, so the returned value respects the 32-bit signed integer range.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log^2 n)` | The outer loop subtracts large doubled chunks, and the inner loop finds the largest chunk by doubling |
| Space | `O(1)` | We only use integer variables |

Here, `n = abs(dividend)`.

For 32-bit integers, this is fast because there are only about 31 useful bit positions.

## Implementation

```python
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        INT_MIN = -2**31
        INT_MAX = 2**31 - 1

        if dividend == INT_MIN and divisor == -1:
            return INT_MAX

        negative = (dividend < 0) != (divisor < 0)

        a = abs(dividend)
        b = abs(divisor)

        quotient = 0

        while a >= b:
            current = b
            count = 1

            while (current << 1) <= a:
                current <<= 1
                count <<= 1

            a -= current
            quotient += count

        if negative:
            quotient = -quotient

        return quotient
```

## Code Explanation

We define the 32-bit bounds:

```python
INT_MIN = -2**31
INT_MAX = 2**31 - 1
```

The only overflow case is:

```python
-2147483648 / -1 = 2147483648
```

That value is too large for a signed 32-bit integer, so we return `INT_MAX`.

```python
if dividend == INT_MIN and divisor == -1:
    return INT_MAX
```

Next, compute the result sign:

```python
negative = (dividend < 0) != (divisor < 0)
```

This is true when one number is negative and the other is positive.

Then use absolute values:

```python
a = abs(dividend)
b = abs(divisor)
```

The main loop runs while another copy of the divisor can still fit:

```python
while a >= b:
```

For each round, start with one copy:

```python
current = b
count = 1
```

Then double both the chunk value and the count while the doubled chunk still fits:

```python
while (current << 1) <= a:
    current <<= 1
    count <<= 1
```

The shift `current << 1` means doubling `current`.

After finding the largest valid chunk, subtract it:

```python
a -= current
```

Then add its count to the quotient:

```python
quotient += count
```

Finally, apply the sign:

```python
if negative:
    quotient = -quotient
```

Return the quotient.

## Testing

```python
def check(dividend: int, divisor: int, expected: int) -> None:
    actual = Solution().divide(dividend, divisor)
    assert actual == expected, (dividend, divisor, actual, expected)

def run_tests():
    check(10, 3, 3)
    check(7, -3, -2)
    check(0, 1, 0)
    check(1, 1, 1)
    check(-10, 3, -3)
    check(10, -3, -3)
    check(-10, -3, 3)
    check(43, 3, 14)
    check(-2147483648, -1, 2147483647)
    check(-2147483648, 1, -2147483648)
    check(-2147483648, 2, -1073741824)
    check(2147483647, 1, 2147483647)

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `10 / 3` | Positive truncation |
| `7 / -3` | Negative truncation toward zero |
| `0 / 1` | Zero dividend |
| `1 / 1` | Small exact division |
| Mixed signs | Checks sign handling |
| `43 / 3` | Multiple doubled chunks |
| `-2^31 / -1` | Overflow case |
| `-2^31 / 1` | Lower bound |
| `-2^31 / 2` | Large negative division |
| `2^31 - 1 / 1` | Upper bound |