29. Divide Two Integers
You receive two integers, dividend and divisor (the divisor is never zero). Compute the quotient dividend / divisor without ever using the multiplication, division, or modulo operators, truncating the result toward zero — so 7 / -3 becomes -2, not -3.
The answer must fit in a signed 32-bit integer: if the true quotient would exceed 2^31 - 1, return 2^31 - 1; if it would fall below -2^31, return -2^31. (With 32-bit inputs, the only quotient that actually overflows is -2^31 / -1.) Addition, subtraction, comparisons, and bit shifts are all fair game.
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10 / 3 = 3.333..., which truncates to 3.
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7 / -3 = -2.333...; truncation moves toward zero, so the answer is -2 rather than -3.
Constraints:
- -2³¹ ≤ dividend, divisor ≤ 2³¹ - 1
- divisor ≠ 0
- Do not use multiplication (*), division (/), or modulo (%).
- If the quotient overflows signed 32 bits, clamp it to 2³¹ - 1 or -2³¹.
Hints:
Strip the signs first: compute with absolute values, remember whether exactly one operand was negative, and reapply the sign at the end. Truncation toward zero then falls out naturally.
Subtracting the divisor once per step is hopeless for quotients near 2 billion. Doubling is not: b, 2b, 4b, 8b... reach any magnitude in about 31 steps, and doubling is just x + x or x << 1 — no multiplication needed.
Greedy peeling: find the largest doubled chunk that still fits under what remains, subtract it, add the matching power of two to the quotient, and repeat (or walk shifts 31 down to 0 in one pass).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: dividend = 10, divisor = 3
Expected output: 3