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 = 3Output: 3
Example 2:
Input: dividend = 7, divisor = -3Output: -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.
只能用加减来实现除法-> recutsion。主要考虑以下几种情况:
1. 溢出 -> 用long
2. 被除数为0 或者 被除数小于除数 -> 返回0
3. 符号问题
time: O(logn), space: O(logn)
class Solution { public int divide(int dividend, int divisor) { int sign = 1; if((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) sign = -1; long longdividend = Math.abs((long)dividend); long longdivisor = Math.abs((long)divisor); if(longdividend == 0 || longdividend < longdivisor) return 0; long longres = helper(longdividend, longdivisor); int res = (int)longres; if(longres > Integer.MAX_VALUE) { res = sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE; } return sign * res; } public long helper(long dividend, long divisor) { if(dividend < divisor) return 0; long sum = divisor; long multiple = 1; while(sum + sum <= dividend) { sum += sum; multiple += multiple; } return multiple + helper(dividend - sum, divisor); }}