Divide Two Integers

medium math bit manipulation

Problem

Given two integers dividend and divisor, divide them without using multiplication, division, or mod, truncating toward zero. Clamp the result to the signed 32-bit range.

Inputdividend = 10, divisor = 3

Output3

10 / 3 = 3.33… → truncated to 3.

dividend

divisor

def divide(dividend, divisor):
    INT_MAX, INT_MIN = (1 << 31) - 1, -(1 << 31)
    if dividend == INT_MIN and divisor == -1: return INT_MAX
    neg = (dividend < 0) ^ (divisor < 0)
    a, b = abs(dividend), abs(divisor)
    q = 0
    while a >= b:
        t, m = b, 1
        while a >= (t << 1):
            t <<= 1; m <<= 1
        a -= t; q += m
    return -q if neg else q

function divide(dividend, divisor) {
  const INT_MAX = 2 ** 31 - 1, INT_MIN = -(2 ** 31);
  if (dividend === INT_MIN && divisor === -1) return INT_MAX;
  const neg = (dividend < 0) !== (divisor < 0);
  let a = Math.abs(dividend), b = Math.abs(divisor);
  let q = 0;
  while (a >= b) {
    let t = b, m = 1;
    while (a >= t * 2) { t *= 2; m *= 2; }
    a -= t; q += m;
  }
  return neg ? -q : q;
}

class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        boolean neg = (dividend < 0) ^ (divisor < 0);
        long a = Math.abs((long) dividend), b = Math.abs((long) divisor);
        long q = 0;
        while (a >= b) {
            long t = b, m = 1;
            while (a >= (t << 1)) { t <<= 1; m <<= 1; }
            a -= t; q += m;
        }
        return (int) (neg ? -q : q);
    }
}

int divide(int dividend, int divisor) {
    if (dividend == INT_MIN && divisor == -1) return INT_MAX;
    bool neg = (dividend < 0) ^ (divisor < 0);
    long a = labs((long) dividend), b = labs((long) divisor);
    long q = 0;
    while (a >= b) {
        long t = b, m = 1;
        while (a >= (t << 1)) { t <<= 1; m <<= 1; }
        a -= t; q += m;
    }
    return (int) (neg ? -q : q);
}

Explanation

We must divide without using *, /, or %. The trick is that division is just repeated subtraction, but plain subtraction is slow, so we subtract in big doubling chunks instead.

First we handle signs: work with the absolute values a and b, and remember separately whether the answer should be negative. There is one special overflow case, INT_MIN / -1, which we clamp to INT_MAX up front.

The core loop: while a >= b, we start with t = b and m = 1, then keep doubling both (t <<= 1, m <<= 1) as long as t still fits in a. This finds the largest multiple of b that is a power of two and still <= a. We subtract that big chunk t from a and add the matching count m to the quotient.

Example: 10 / 3. With b = 3, doubling gives t = 6 (m = 2) since 12 > 10 stops it. Subtract: a = 4, q = 2. Next round t = 3 (m = 1), subtract: a = 1, q = 3. Now 1 < 3 so we stop with quotient 3.

Doubling means each chunk removes a large piece at once, so we finish in a logarithmic number of steps rather than subtracting one b at a time.

Time: O(log² n) Space: O(1)