29. Divide Two Integers
Divide Two Integers
Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.
The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.
Return the quotient after dividing dividend by divisor.
Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -231.
Example 1:
Input: dividend = 10, divisor = 3 Output: 3 Explanation: 10/3 = 3.33333.. which is truncated to 3.
Example 2:
Input: dividend = 7, divisor = -3 Output: -2 Explanation: 7/-3 = -2.33333.. which is truncated to -2.
Constraints:
-231 <= dividend, divisor <= 231 - 1divisor != 0
Approach) Naive
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.
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
};Approach) Math
- A variable quotient will keep the track of answer.
- A while loop will check the condition dividend >= divisor
- Inside this while loop, we will have one variable shift which will left shift the divisor by one bit and check if the result is less than the dividend. This will repeat until the condition is false.
- Once, we are out of inner loop, then we will add the number of times we shifted to the quotient.
- Also, we will now subtract the result of shifting to divisor from the dividend for the next iteration. Remember that since in the while loop the value of shifting had gone beyond the dividend, the value we need to subtract is one bit less shifted.
- We will repeat the process unless we reach to the point where divisor is greater than dividend.
- You must be wondering that why are we shifting the bits? The answer is, one left shift bit means the number is doubled. And since we cannot use multiplication, we are using left shifting.
Code:
var divide = function (dividend, divisor) {
const MAX = 2147483647;
const MIN = -2147483648;
// Check for overflow
if (divisor === 0 || (dividend === MIN && divisor === -1)) {
return MAX;
}
if (divisor === dividend) {
return 1;
}
// Sign of result
const sign = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0) ? -1 : 1;
// Quotient
let quotient = 0;
// Take the absolute value
let absoluteDividend = Math.abs(dividend);
let absoluteDivisor = Math.abs(divisor);
// Loop until the dividend is greater than divisor
while (absoluteDividend >= absoluteDivisor) {
// This represents the number of bits shifted or
// how many times we can double the number
let shift = 0;
let shiftedDivisor = absoluteDivisor;
while (absoluteDividend >= shiftedDivisor) {
shift++;
shiftedDivisor = absoluteDivisor << shift;
// To handle overflow using left shift operator in JS
if (shiftedDivisor < 0) {
break;
}
}
// Add the number of times we shifted to the quotient
quotient += (1 << (shift - 1));
// Update the dividend for the next iteration
absoluteDividend -= absoluteDivisor << (shift - 1);
}
return sign === -1 ? -quotient : quotient;
};Time Complexity
Since the divisor is increasing exponentially, the time complexity will be O(log n).
Space Complexity
No internal data structure has been used in the intermediate computations, the space complexity will be O(1).
Conclusion
That’s all folks! In this post, we solved LeetCode problem #29. Divide Two Integers
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.
In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!
Comments
Post a Comment