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
dividendanddivisor, divide two integers without using multiplication, division, and mod operator.Return the quotient after dividing
dividendbydivisor.The integer division should truncate toward zero, which means losing its fractional part. For example,
truncate(8.345) = 8andtruncate(-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 returns2^31 − 1when 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 - 1divisor != 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)
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;
}
};
This content originally appeared on DEV Community and was authored by seanpgallivan
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/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.