Given two integers dividend and divisor, divide them without using multiplication, division, or the modulo operator, and return the quotient after truncating toward zero (e.g. 8 / -3 = -2).
The result must fit in a signed 32-bit integer. If it would overflow — which happens only for -2^31 / -1 — return 2^31 - 1 instead.
2^31, but the largest signed 32-bit integer is 2^31 - 1. It's the only input pair that overflows, so it's clamped to 2^31 - 1.abs(-2^31) is 2^31, which doesn't fit a 32-bit int. Promoting to 64-bit lets the magnitudes and doubled chunks be represented without overflow.*, /, and %. You can double with + or a left shift and halve with a right shift, as long as you respect each language's integer width.a after the loop is |dividend| mod |divisor|; give it the dividend's sign for a truncated remainder.Input: dividend = 10, divisor = 3 Output: 3 10 / 3 = 3.333..., truncated toward zero to 3.
Input: dividend = 7, divisor = -3 Output: -2 7 / -3 = -2.333..., truncated toward zero to -2.
Input: dividend = -2147483648, divisor = -1 Output: 2147483647 The true result 2^31 overflows a signed 32-bit int, so it is clamped to 2^31 - 1.
- -2^31 <= dividend, divisor <= 2^31 - 1 - divisor != 0 - The quotient is truncated toward zero.
Division is just "how many times does the divisor fit?" — repeated subtraction. But subtracting one divisor at a time can take up to two billion steps. The fix is to subtract in exponentially growing chunks, and then carefully handle signs and the single overflow case.
x + x — to build big chunks fast.-2^31 has no positive counterpart in 32-bit, and why -2^31 / -1 must be clamped.“Which operators are off-limits?”
Multiplication, division, and modulo. Addition, subtraction, comparison, and bit shifts are fair game.
“How is a non-exact quotient rounded?”
Truncated toward zero, so 7 / -3 is -2, not -3.
“Can the divisor be zero?”
No — the divisor is guaranteed non-zero.
“What's the one overflow case?”
-2^31 / -1 mathematically equals 2^31, which doesn't fit a signed 32-bit int — clamp it to 2^31 - 1.
Division is repeated subtraction, but one-at-a-time is O(quotient) — up to two billion steps.
So I'll subtract the largest doubling of the divisor that still fits, then repeat — that's logarithmic.
I'll work in absolute values with a wider type, reapply the sign at the end, and special-case -2^31 / -1.
Worked example — 43 / 3
remaining = 43 biggest chunk of 3 that fits: 3->6->12->24 (48 too big) = 24 (= 3 x 8) subtract 24 -> remaining 19, quotient += 8 biggest chunk: 3->6->12 (24 too big) = 12 (= 3 x 4) subtract 12 -> remaining 7, quotient += 4 biggest chunk: 3->6 (12 too big) = 6 (= 3 x 2) subtract 6 -> remaining 1, quotient += 2 1 < 3, stop. quotient = 8 + 4 + 2 = 14 (43 / 3 = 14 rem 1)
Removing a single divisor per step is O(quotient), which can reach 2^31. You need to remove exponentially large chunks, not constant ones.
Since you can't multiply, grow the chunk by adding it to itself: b -> 2b -> 4b -> ..., doubling a counter 1 -> 2 -> 4 -> ... alongside. Subtract the largest chunk that fits, then repeat on the remainder. This is O(log n) steps.
Work with the absolute values so the loop logic stays positive, then negate the result if exactly one input was negative. Because abs(-2^31) doesn't fit a 32-bit int, compute in a wider type — and clamp the single overflow, -2^31 / -1, to 2^31 - 1.
| Doubling, restart | Doubling, one descent | |
|---|---|---|
| Idea | Rebuild the biggest chunk from scratch each round | Build the biggest chunk once, then halve down through it |
| Time | O(log^2 n) | O(log n) |
| Space | O(1) | O(1) |
Both avoid the forbidden operators and use constant space; the descending version just doesn't rebuild the chunk each round. Full code is in the Approaches selector below.
Key takeaway
Division without / is repeated subtraction sped up with doubling: subtract the largest divisor x 2^k that fits, add 2^k to the quotient, and shrink. Handle signs via absolute values in a wider type, and clamp the one overflow case, -2^31 / -1, to 2^31 - 1.
if dividend == -2^31 and divisor == -1: return 2^31 - 1
work with a = |dividend|, b = |divisor| (in a wide type)
quotient = 0
while a >= b:
chunk, count = b, 1
while chunk + chunk <= a:
chunk += chunk; count += count
a -= chunk; quotient += count
apply the sign to quotient