Solution: Divide Two Integers (ver. 2)
Tags: algorithms, javascript, java, python
Published: 2021-02-27 21:49:29

*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 second version of a solution for this problem. Some have questioned whether or not [the bitwise shifts used in the first version](https://dev.to/seanpgallivan/solution-divide-two-integers-5dcd) should count as multiplication/division, so this is an alternate solution taking advantage of the algebraic qualities of logarithms.*

---

#### [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))

For those who consider bitwise shifts to be too close to multiplication/division, we can instead use the rules of **logarithms** to our advantage:
```js
  if:  exp(log(c) = c                   // Logarithmic rule #1
  if:  log(a / b) = log(a) - log(b)     // Logarithmic rule #2

then:  a / b = exp(log(a / b))          // From rule #1
       a / b = exp(log(a) - log(b))     // From rule #2

       (if m and n are > 0)
```
Since we'll have to use the absolute values of **A** and **B**, we'll have to define some edge cases to deal with the difference in lower and upper constraints placed by a **32-bit** integer (without resorting to using long variable storage) as well as the one edge case dictated by the instructions.

Finally, we'll also have to apply a **floor()** to the result to truncate the decimal before we **return ans**, while remembering to adjust for the signs of the input.

---

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

Python handles numbers larger than **32-bit** internally, even for their **log()** and **exp()** functions, so we can skip all but the mandated edge case.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var divide = function(A, B) {
    let ans = 0
    if (B === -2147483648) return A === B
    if (A === -2147483648)
        if (B === 1) return -2147483648
        else if (B === -1) return 2147483647
        else A += Math.abs(B), ans++
    ans += Math.floor(Math.exp(Math.log(Math.abs(A)) - Math.log(Math.abs(B))))
    return A > 0 === B > 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 == 0: return 0
        if A == -2147483648 and B == -1: return 2147483647
        ans = math.floor(math.exp(math.log(abs(A)) - math.log(abs(B))))
        return ans if (A > 0) == (B > 0) else -ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int divide(int A, int B) {
        int ans = 0;
        if (B == -2147483648) return A == B ? 1 : 0;
        if (A == -2147483648) {
            if (B == 1) return -2147483648;
            if (B == -1) return 2147483647;
            A += Math.abs(B);
            ans++;
        }
        ans += Math.floor(Math.exp(Math.log(Math.abs(A)) - Math.log(Math.abs(B))));
        return A > 0 == B > 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;
        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++;
        ans += floor(exp(log(abs(A)) - log(abs(B))));
        return A > 0 == B > 0 ? ans : -ans;
    }
};
```