Divide two numbers without multiplication and division
MediumSubtract the largest shifted divisor
Problem
Divide two integers without using multiplication, division, or mod; return the quotient (truncated).
Subtract shifted copies of the divisor (doubling each time) — like long division in binary.
The idea
Repeatedly find the largest multiple of the divisor formed by shifting it left that still fits in the remaining dividend, subtract it, and add the matching power of two to the quotient. That is long division in base two, so it runs in O(log n) subtractions.
The trick
- Work with absolute values in 64-bit, then apply the sign at the end.
- INT_MIN / -1 overflows — clamp it to INT_MAX explicitly.
- Repeated plain subtraction would be O(n) and far too slow.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — dividend=22, divisor=3 Values: 22, 3.
1q=02while dividend>=divisor:3 temp=divisor; m=14 while dividend >= (temp<<1): temp<<=1; m<<=15 dividend-=temp; q+=m6return q (with sign)Input
- array
- [22, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- dividend = 10, divisor = 3
- Output:
- 3
- Explanation:
- 10/3 truncates toward zero → 3.
Example 2
- Input:
- dividend = 7, divisor = -2
- Output:
- -3
- Explanation:
- Signs differ → -3.
Example 3
- Input:
- dividend = 0, divisor = 5
- Output:
- 0
- Explanation:
- Zero divided by anything is 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.