Problem
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.
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Note:
- Both dividend and divisor will be 32-bit signed integers.
- The divisor will never be 0.
- Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.
Solution
/**
* @param {number} dividend
* @param {number} divisor
* @return {number}
*/
var divide = function(dividend, divisor) {
var did = Math.abs(dividend);
var dis = Math.abs(divisor);
var sign = (divisor > 0 && dividend > 0) || (divisor < 0 && dividend < 0);
var res = 0;
var arr = [dis];
if (dividend === 0 || did < dis) return 0;
if (divisor === -1 && dividend === -2147483648) return 2147483647;
if (dis === 1) return divisor > 0 ? dividend : -dividend;
while (arr[arr.length - 1] < did) arr.push(arr[arr.length - 1] + arr[arr.length - 1]);
for (var i = arr.length - 1; i >= 0; i--) {
if (did >= arr[i]) {
did -= arr[i];
res += i === 0 ? 1 : 2 << (i - 1);
}
}
return sign ? res : -res;
};
Explain:
- 要注意
-2147483648 / -1
越界的情况 - 核心就是
dividend -= divisor << i; result += 2 << (i - 1);
- 其它语言有
long
、long long
类型可以保证divisor << i
不越界,但是 js 没有。比如2 << 29
是1073741824
,2 << 30
就越界了,不会得到预期的结果。我这里是用加法提前计算好divisor << i
。
Complexity:
- Time complexity : O(log(n)).
- Space complexity : O(log(n)).