Solution: Divide Two Integers (ver. 2)

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

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

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

For those who consider bitwise shifts to be too close to multiplication/division, we can instead use the rules of logarithms to our advantage:

  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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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;
    }
};