Divide Two Integers Without Multiplication, Division or Mod
Solve this Problemdividend 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.
Test Case 1:
Test Case 2:
Test Case 3:
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]
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Repeated Subtraction
BruteSubtract the divisor's magnitude from the dividend's magnitude one copy at a time, counting how many subtractions it takes to run out. Correct, but for a large dividend and a small divisor this can mean billions of individual subtractions.
O(dividend / divisor)O(1)1class Solution {
2 public int divide(int dividend, int divisor) {
3 if (dividend == Integer.MIN_VALUE && divisor == -1) {
4 return Integer.MAX_VALUE;
5 }
6 boolean negative = (dividend < 0) != (divisor < 0);
7 long a = Math.abs((long) dividend);
8 long b = Math.abs((long) divisor);
9 long quotient = 0;
10 while (a >= b) {
11 a -= b;
12 quotient++;
13 }
14 return negative ? (int) -quotient : (int) quotient;
15 }
16}Optimal — Exponential Bit-Shift Search
OptimalInstead of subtracting the divisor one copy at a time, subtract the largest power-of-two multiple of it that still fits: keep doubling the chunk being subtracted (first check if twice the divisor still fits, then four times, then eight) until doubling again would overshoot. Subtract that chunk in one step, add its matching power of two to the quotient, and repeat on what's left — roughly one step per bit of the quotient instead of one step per unit.
O(log² n)O(1)1class Solution {
2 public int divide(int dividend, int divisor) {
3 if (dividend == Integer.MIN_VALUE && divisor == -1) {
4 return Integer.MAX_VALUE;
5 }
6 boolean negative = (dividend < 0) != (divisor < 0);
7 long a = Math.abs((long) dividend);
8 long b = Math.abs((long) divisor);
9 long quotient = 0;
10 while (a >= b) {
11 long temp = b;
12 long multiple = 1;
13 while (a >= (temp << 1)) {
14 temp <<= 1;
15 multiple <<= 1;
16 }
17 a -= temp;
18 quotient += multiple;
19 }
20 return negative ? (int) -quotient : (int) quotient;
21 }
22}