Divide two integers without using multiplication, division, or mod operators. Return the quotient truncated toward zero. If overflow, return INT_MAX.
Input: dividend=10, divisor=3 → Output: 3Input: dividend=7, divisor=-3 → Output: -2
Use bit shifting for fast division. Double the divisor until exceeding dividend, then subtract and repeat.
- Handle overflow edge case: INT_MIN / -1 = overflow.
- Work with longs. Determine sign.
- For each power p from 31 down to 0: if divisor << p <= dividend, subtract and add 2^p to quotient.
- Apply sign.
class Solution {
public int divide(int dividend, int divisor) {
if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
long dvd = Math.abs((long)dividend), dvs = Math.abs((long)divisor);
int sign = (dividend > 0) == (divisor > 0) ? 1 : -1;
long quotient = 0;
for (int shift = 31; shift >= 0; shift--) {
if ((dvs << shift) <= dvd) { quotient += 1L << shift; dvd -= dvs << shift; }
}
return sign * (int) quotient;
}
}
- Time Complexity: O(log^2 N)
- Space Complexity: O(1)