## DEV Community is a community of 700,827 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # Solution: Divide Two Integers (ver. 1) 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 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.

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

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:

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

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

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

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