Divide Two Integers Without Multiplication, Division or Mod
Implement divide
Given two integers
dividend and divisor, compute their integer division — truncated toward zero — without using the *, /, or % operators. If the true quotient would overflow the 32-bit signed integer range (which only happens when dividing the most negative representable value by -1), clamp the result to the range's maximum instead.
Repeatedly subtracting the divisor counts how many times it fits, but one subtraction at a time is as slow as the quotient is large. Doubling the chunk being subtracted — first check if twice the divisor still fits, then four times, then eight — finds the largest power-of-two multiple that fits in one step, cutting the work down to roughly one step per bit of the quotient instead of one step per unit.
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Example 3:
Input: dividend = -2147483648, divisor = -1
Output: 2147483647
+ 12 hidden test cases run on Submit.
Constraints:
- ●
-2³¹ ≤ dividend ≤ 2³¹ − 1 - ●
-2³¹ ≤ divisor ≤ 2³¹ − 1 - ●
divisor ≠ 0 - ●
The result is truncated toward zero; if it would overflow the 32-bit signed range, it is clamped to [-2³¹, 2³¹ − 1]
dividend =
10
divisor =
3