# Divide Two Integers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/divide-two-integers)
Canonical: https://scaleengineer.com/dsa/problems/divide-two-integers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zepto](https://scaleengineer.com/companies/zepto), [Nextdoor](https://scaleengineer.com/companies/nextdoor)
---
## Problem
Given two integers `dividend` and `divisor`, divide two integers **without** using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, `8.345` would be truncated to `8`, and `-2.7335` would be truncated to `-2`.

Return _the **quotient** after dividing_ `dividend` _by_ `divisor`.

**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, if the quotient is **strictly greater than** `231 - 1`, then return `231 - 1`, and if the quotient is **strictly less than** `-231`, then return `-231`.

**Example 1:**

**Input:** dividend = 10, divisor = 3
**Output:** 3
**Explanation:** 10/3 = 3.33333.. which is truncated to 3.

**Example 2:**

**Input:** dividend = 7, divisor = -3
**Output:** -2
**Explanation:** 7/-3 = -2.33333.. which is truncated to -2.

**Constraints:**

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

# Approaches
## Repeated Subtraction
This is the most intuitive and straightforward approach, directly simulating the fundamental definition of division. Division can be thought of as how many times you can subtract the divisor from the dividend. We repeatedly subtract the divisor from the dividend until the dividend becomes smaller than the divisor, counting the number of subtractions.
**Time:** O(N/M) · **Space:** O(1)
**Pros:** Very simple to understand and implement.; It's a direct translation of the mathematical definition of division.
**Cons:** Extremely inefficient for large dividends and small divisors.; Will not pass the time limits on most online judges, resulting in a Time Limit Exceeded (TLE) error.
### Explanation
First, we handle the sign of the result. The quotient is negative if and only if the dividend and divisor have opposite signs. We can determine this using an XOR operation `(dividend < 0) ^ (divisor < 0)` and store it.

To simplify the main logic, we work with the absolute values of the dividend and divisor. A crucial edge case is `Integer.MIN_VALUE`, whose absolute value cannot be stored in a 32-bit signed integer. We must convert the numbers to a 64-bit `long` type before taking the absolute value to prevent overflow.

We also need to handle the specific overflow case where `dividend` is `Integer.MIN_VALUE` and `divisor` is `-1`. The result `2^31` exceeds `Integer.MAX_VALUE`, so we must return `Integer.MAX_VALUE` as per the problem description.

The core of the algorithm is a loop that subtracts the absolute value of the divisor from the absolute value of the dividend and increments a quotient counter until the dividend is no longer greater than or equal to the divisor.

Finally, we apply the pre-calculated sign to the resulting quotient before returning it.

```java
class Solution {
    public int divide(int dividend, int divisor) {
        // Handle the specific overflow case
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        // Determine the sign of the quotient
        boolean isNegative = (dividend < 0) ^ (divisor < 0);

        // Use long to handle the absolute value of Integer.MIN_VALUE
        long absDividend = Math.abs((long) dividend);
        long absDivisor = Math.abs((long) divisor);

        int quotient = 0;
        while (absDividend >= absDivisor) {
            absDividend -= absDivisor;
            quotient++;
        }

        return isNegative ? -quotient : quotient;
    }
}
```
### Algorithm
- Handle the overflow case: if `dividend` is `Integer.MIN_VALUE` and `divisor` is `-1`, return `Integer.MAX_VALUE`.
- Determine the sign of the result. Store it in a boolean variable `isNegative`.
- Convert both `dividend` and `divisor` to `long` and take their absolute values to avoid overflow and simplify subtraction.
- Initialize a `quotient` variable to 0.
- Start a loop that continues as long as the absolute dividend is greater than or equal to the absolute divisor.
- Inside the loop, subtract the absolute divisor from the absolute dividend.
- Increment the `quotient`.
- After the loop, if `isNegative` is true, return `-quotient`. Otherwise, return `quotient`.

## Repeated Exponential Subtraction
The naive repeated subtraction is slow because we only subtract the divisor one at a time. We can significantly speed this up by subtracting multiples of the divisor that are powers of two. Instead of `dividend - divisor`, we find the largest power of two, `k`, such that `divisor * 2^k` is still less than or equal to the dividend. We then subtract this value and add `2^k` to our quotient. This process is repeated with the remainder.
**Time:** O((log N)^2) · **Space:** O(1)
**Pros:** Much more efficient than the naive approach and passes typical time limits.; Uses efficient bitwise operations.
**Cons:** The logic is more complex with nested loops.; Still not the most optimal solution.
### Explanation
This approach is an optimization over the simple subtraction method. It's analogous to how we perform long division by hand, where we try to find the largest multiple of the divisor that fits into the current part of the dividend. Here, we use powers of two for the multiples because they can be calculated efficiently using bitwise left shifts (`<<`).

As with the previous approach, we first handle the sign and edge cases, and convert the inputs to `long` to work with their absolute values.

The main logic is an outer loop that continues as long as the remaining dividend is greater than or equal to the divisor.

Inside this loop, an inner loop finds the largest multiple of the divisor of the form `divisor * 2^k` that is less than or equal to the current dividend. It does this by starting with `temp = divisor` and `multiple = 1`, and repeatedly doubling both (`temp <<= 1`, `multiple <<= 1`) until `temp` exceeds the dividend.

Once the largest such multiple is found, we subtract `temp` from the dividend and add the corresponding `multiple` to our total quotient.

The outer loop then continues with the new, smaller dividend. This process effectively performs a binary search for the quotient.

```java
class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;

        long ldividend = Math.abs((long) dividend);
        long ldivisor = Math.abs((long) divisor);

        int quotient = 0;
        while (ldividend >= ldivisor) {
            long temp = ldivisor;
            long multiple = 1;
            // Find the largest multiple of divisor (as power of 2)
            // that is less than or equal to dividend.
            while (ldividend >= (temp << 1)) {
                temp <<= 1;
                multiple <<= 1;
            }
            // Subtract this multiple from dividend
            ldividend -= temp;
            // Add the power of 2 to the quotient
            quotient += multiple;
        }

        return sign * quotient;
    }
}
```
### Algorithm
- Handle the overflow case (`Integer.MIN_VALUE / -1`) and determine the sign of the result.
- Convert `dividend` and `divisor` to their absolute values using `long`.
- Initialize `quotient = 0`.
- While `ldividend >= ldivisor`:
  a. Initialize `temp = ldivisor` and `multiple = 1`.
  b. In an inner loop, keep doubling `temp` and `multiple` (using left shifts) as long as `ldividend` is greater than or equal to the doubled `temp`.
  c. Subtract the final `temp` from `ldividend`.
  d. Add the final `multiple` to the `quotient`.
- Apply the sign to the `quotient` and return the result.

## Bit Manipulation (Binary Long Division)
This is the most efficient approach and mimics the process of long division in binary. We can determine the bits of the quotient one by one, from the most significant bit to the least significant bit. For each bit position `i` (from 31 down to 0), we check if the dividend is large enough to subtract the divisor shifted by `i` positions (`divisor << i`). If it is, then the `i`-th bit of the quotient is 1.
**Time:** O(1) · **Space:** O(1)
**Pros:** The most efficient solution with constant time complexity for fixed-size integers.; Elegant use of bit manipulation that mirrors hardware division algorithms.
**Cons:** The logic can be less intuitive than the other approaches if one is not comfortable with bitwise operations.; Requires careful handling of types (`long`) and bit shifts to avoid overflow issues.
### Explanation
The core idea is to build the quotient bit by bit. A 32-bit integer quotient can be represented as `q = b_31*2^31 + b_30*2^30 + ... + b_0*2^0`, where `b_i` is either 0 or 1. The division equation is `dividend = quotient * divisor`. Substituting the binary representation of the quotient, we get `dividend = (b_31*2^31 + ... + b_0*2^0) * divisor`.

We can find each bit `b_i` starting from the most significant one, `b_31`. We check if `dividend >= divisor * 2^i`. If this condition holds, it means the `i`-th bit of the quotient must be 1. We then set the `i`-th bit in our result (`quotient |= (1 << i)`) and subtract `divisor * 2^i` from the dividend to account for this part of the quotient. We then proceed to check the next bit, `i-1`, with the updated, smaller dividend.

Again, we first handle signs and edge cases, using `long` to manage absolute values safely.

The algorithm iterates from `i = 31` down to `0`. In each iteration, it checks if the current `ldividend` is greater than or equal to `ldivisor << i`. A safer way to perform this check to avoid `ldivisor << i` from overflowing is `(ldividend >> i) >= ldivisor`.

If it is, we subtract `ldivisor << i` from `ldividend` and add `1L << i` to our `long` quotient. Using `1L` is important to prevent `1 << 31` from being interpreted as a negative number.

After the loop finishes, we have the absolute value of the quotient, to which we apply the sign.

```java
class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;

        long ldividend = Math.abs((long) dividend);
        long ldivisor = Math.abs((long) divisor);

        long quotient = 0;
        for (int i = 31; i >= 0; i--) {
            // Check if we can subtract (ldivisor << i) from ldividend
            // This check is safer than `ldividend >= (ldivisor << i)` to avoid overflow
            if ((ldividend >> i) >= ldivisor) {
                // Add 2^i to the quotient
                quotient += (1L << i);
                // Subtract the value from the dividend
                ldividend -= (ldivisor << i);
            }
        }

        return (int) (sign * quotient);
    }
}
```
### Algorithm
- Handle the overflow case (`Integer.MIN_VALUE / -1`) and determine the sign.
- Convert `dividend` and `divisor` to their absolute values using `long`.
- Initialize a `long` quotient to 0.
- Iterate a loop for `i` from 31 down to 0 (for each bit of the potential quotient).
- Inside the loop, check if `ldividend` shifted right by `i` is greater than or equal to `ldivisor`. This is equivalent to checking `ldividend >= (ldivisor << i)` but avoids overflow when shifting `ldivisor`.
- If the condition is true, it means the `i`-th bit of the quotient is 1. Add `(1L << i)` to the `quotient` and subtract `(ldivisor << i)` from `ldividend`.
- After the loop, apply the sign to the `long` quotient.
- Cast the final result to `int` and return.

# Solutions
### CSharp

```csharp
public class Solution {
    public int Divide(int a, int b) {
        if (b == 1) {
            return a;
        }
        if (a == int.MinValue && b == -1) {
            return int.MaxValue;
        }
        bool sign = (a > 0 && b > 0) || (a < 0 && b < 0);
        a = a > 0 ? -a : a;
        b = b > 0 ? -b : b;
        int ans = 0;
        while (a <= b) {
            int x = b;
            int cnt = 1;
            while (x >= (int.MinValue >> 1) && a <= (x << 1)) {
                x <<= 1;
                cnt <<= 1;
            }
            ans += cnt;
            a -= x;
        }
        return sign ? ans : -ans;
    }
}
```

### Java

```java
class Solution { public int divide ( int a , int b ) { if ( b == 1 ) { return a ; } if ( a == Integer . MIN_VALUE && b == - 1 ) { return Integer . MAX_VALUE ; } boolean sign = ( a > 0 && b > 0 ) || ( a < 0 && b < 0 ); a = a > 0 ? - a : a ; b = b > 0 ? - b : b ; int ans = 0 ; while ( a <= b ) { int x = b ; int cnt = 1 ; while ( x >= ( Integer . MIN_VALUE >> 1 ) && a <= ( x << 1 )) { x <<= 1 ; cnt <<= 1 ; } ans += cnt ; a -= x ; } return sign ? ans : - ans ; } }
```

### Python

```python
class Solution : def divide ( self , a : int , b : int ) -> int : if b == 1 : return a if a == - ( 2 ** 31 ) and b == - 1 : return 2 ** 31 - 1 sign = ( a > 0 and b > 0 ) or ( a < 0 and b < 0 ) a = - a if a > 0 else a b = - b if b > 0 else b ans = 0 while a <= b : x = b cnt = 1 while x >= ( - ( 2 ** 30 )) and a <= ( x << 1 ): x <<= 1 cnt <<= 1 a -= x ans += cnt return ans if sign else - ans
```

### CPP

```cpp
class Solution {
public:
  int divide(int a, int b) {
    if (b == 1) {
      return a;
    }
    if (a == INT_MIN && b == -1) {
      return INT_MAX;
    }
    bool sign = (a > 0 && b > 0) || (a < 0 && b < 0);
    a = a > 0 ? -a : a;
    b = b > 0 ? -b : b;
    int ans = 0;
    while (a <= b) {
      int x = b;
      int cnt = 1;
      while (x >= (INT_MIN >> 1) && a <= (x << 1)) {
        x <<= 1;
        cnt <<= 1;
      }
      ans += cnt;
      a -= x;
    }
    return sign ? ans : -ans;
  }
};

```