Solution: Divide Two Integers

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.

Leetcode Problem #29 (Medium): Divide Two Integer…


This content originally appeared on DEV Community and was authored by seanpgallivan

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.

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
};
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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)
            if (A == B) return 1;
            else return 0;
        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;
    }
};
Enter fullscreen mode Exit fullscreen mode


This content originally appeared on DEV Community and was authored by seanpgallivan


Print Share Comment Cite Upload Translate Updates
APA

seanpgallivan | Sciencx (2021-02-27T12:35:30+00:00) Solution: Divide Two Integers. Retrieved from https://www.scien.cx/2021/02/27/solution-divide-two-integers/

MLA
" » Solution: Divide Two Integers." seanpgallivan | Sciencx - Saturday February 27, 2021, https://www.scien.cx/2021/02/27/solution-divide-two-integers/
HARVARD
seanpgallivan | Sciencx Saturday February 27, 2021 » Solution: Divide Two Integers., viewed ,<https://www.scien.cx/2021/02/27/solution-divide-two-integers/>
VANCOUVER
seanpgallivan | Sciencx - » Solution: Divide Two Integers. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2021/02/27/solution-divide-two-integers/
CHICAGO
" » Solution: Divide Two Integers." seanpgallivan | Sciencx - Accessed . https://www.scien.cx/2021/02/27/solution-divide-two-integers/
IEEE
" » Solution: Divide Two Integers." seanpgallivan | Sciencx [Online]. Available: https://www.scien.cx/2021/02/27/solution-divide-two-integers/. [Accessed: ]
rf:citation
» Solution: Divide Two Integers | seanpgallivan | Sciencx | https://www.scien.cx/2021/02/27/solution-divide-two-integers/ |

Please log in to upload a file.




There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.