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