## DEV Community is a community of 674,199 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # Solution: Divide Two Integers (ver. 2) seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.

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.

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

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

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

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

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