Solution: Divide Two Integers (ver. 1)

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.

---

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

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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