Divide Two Integers
Medium · Math · Math · Bit Manipulation
Problem
Given two integers dividend and divisor, return the quotient of dividend / divisor truncated toward zero, without using multiplication, division or the modulo operator.
Truncating toward zero means 7 / -2 gives -3, not -4.
Assume you can only store signed 32-bit integers. If the true quotient is larger than 2^31 - 1, return 2^31 - 1; if it is smaller than -2^31, return -2^31.
Examples
Input: dividend = 20, divisor = 6 Output: 3
20 / 6 = 3.33..., truncated to 3.
Input: dividend = 7, divisor = -2 Output: -3
-3.5 truncated toward zero is -3.
Input: dividend = -2147483648, divisor = -1 Output: 2147483647
The exact result 2^31 does not fit, so it is capped at 2^31 - 1.
Constraints
- -2^31 <= dividend, divisor <= 2^31 - 1
- divisor != 0
Approaches
- Baseline: rebuild the biggest chunk every round — time O(log² q), space O(1)
Follow-up
The table is the binary expansion of the quotient, found from the top bit down: exactly how hardware dividers and long division work. The use cases run it backwards to multiply with only addition, and keep the leftover to get the remainder too.
Related problems
Start free on Cariara · Coding problems · System design studio
