Solution: Divide Two Integers (ver. 1)
Tags: algorithms, javascript, java, python
Published: 2021-02-27 12:35:30

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/divide-two-integers/discuss/1085017).*

---

*__Note__: This is my first version of a solution for this problem. Some have questioned whether or not the bitwise shifts used in this version should count as multiplication/division, so I've also posted [an alternate solution taking advantage of the algebraic qualities of logarithms](https://dev.to/seanpgallivan/solution-divide-two-integers-ver-2-26pp).*

---

#### [Leetcode Problem #29 (*Medium*): Divide Two Integers](https://leetcode.com/problems/divide-two-integers/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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: `[−2^31,  2^31 − 1]`. For this problem, assume that your function returns `2^31 − 1` when the division result overflows.


---

#### ***Examples:***
>
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:***
>
 - `-2^31 <= dividend, divisor <= 2^31 - 1`
 - `divisor != 0`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

The naive approach here would be to use a loop to just work down the difference between the dividend (**A**) and the divisor (**B**) through subtraction, but that's obviously not a very efficient solution.

Instead, we can use **bit manipulation** to simulate multiplication/division. Since a **bitwise shift** to the left is the equivalent of a multiplication by **2**, if we count how many times we can bitwise shift **B** to the left while still staying under **A**, then we can quickly work out a chunk of the solution. All that's left is to start over with the remaining amount of **A** and repeat this process, adding the results to our answer (**ans**) as we go.

Of course, negative numbers will play havoc with our bitwise shifting, so we should first extract the **sign** difference and then use only positive numbers for **A** and **B**.

There's also the stated edge case, which only occurs at one permutation of **A** and **B**, so we can handle that at the outset.

---

#### ***Implementation:***

Javascript and Python both handle numbers larger than **32-bit** internally, and Java requires only a small change to the conditions on its loops to avoid an issue.

C++, on the other hand, adheres strictly to the **32-bit** limit, so we have to define a few more edge cases to avoid exceeding these boundaries. That does allow us to simplify the code for both loops, however.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var divide = function(A, B) {
    if (A === -2147483648 && B === -1) return 2147483647
    let ans = 0, sign = 1
    if (A < 0) A = -A, sign = -sign
    if (B < 0) B = -B, sign = -sign
    if (A === B) return sign
    for (let i = 0, val = B; A >= B; i = 0, val = B) {
        while (val > 0 && val <= A) val = B << ++i
        A -= B << i - 1, ans += 1 << i - 1
    }
    return sign < 0 ? -ans : ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def divide(self, A: int, B: int) -> int:
        if A == -2147483648 and B == -1: return 2147483647
        ans, sign = 0, 1
        if A < 0: A, sign = -A, -sign
        if B < 0: B, sign = -B, -sign
        if A == B: return sign
        while A >= B:
            b = 0
            while B << b <= A: b += 1
            A -= B << b - 1
            ans += 1 << b - 1
        return -ans if sign < 0 else ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int divide(int A, int B) {
        if (A == -2147483648 && B == -1) return 2147483647;
        int ans = 0, sign = A > 0 == B > 0 ? 1 : -1;
        if (A < 0) A = -A;
        if (B < 0) B = -B;
        if (A == B) return sign;
        for (int i = 0, val = B; A - B >= 0; i = 0, val = B) {
            while (val > 0 && A - val >= 0) val = B << ++i;
            A -= B << i - 1;
            ans += 1 << i - 1;
        }
        return sign < 0 ? -ans : ans;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int divide(int A, int B) {
        int ans = 0, sign = A > 0 == B > 0 ? 1 : -1;
        if (B == -2147483648) return A == B;
        if (A == -2147483648)
            if (B == 1) return -2147483648;
            else if (B == -1) return 2147483647;
            else A += abs(B), ans++;
        A = abs(A), B = abs(B);
        for (int i = 0; A >= B; i = 0) {
            while (A >> i >= B) i++;
            A -= B << i - 1, ans += 1 << i - 1;
        }
        return sign < 0 ? -ans : ans;
    }
};
```