Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
February 27, 2021 12:35 pm GMT

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

Original Link: https://dev.to/seanpgallivan/solution-divide-two-integers-5dcd

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To