Divide Two Integers

Share

Divide two integers without using multiplication, division, or mod operators. Return the quotient truncated toward zero. If overflow, return INT_MAX.

Example 1
Input: dividend=10, divisor=3 → Output: 3
Example 2
Input: dividend=7, divisor=-3 → Output: -2

Solution Approach

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.
Java
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)