Divide two integers without *, / or %
Problem
Divide dividend by divisor without using multiplication, division or mod, and truncate the result toward zero. Clamp the result to the 32-bit signed range.
Example 1
Input: dividend = 10, divisor = 3 Output: 3
Example 2
Input: dividend = 7, divisor = -3 Output: -2
Also asked as: Divide two integers without using multiplication, division and mod operator
Test cases
Case 1
Input: 10, 3 Expected: 3
Case 2
Input: 7, -3 Expected: -2
Case 3
Input: -7, 2 Expected: -3
Case 4
Input: 0, 5 Expected: 0
Case 5
Input: -2147483648, -1 Expected: 2147483647
View solutionHide solution1 approach
1. Repeated doubling of the divisor
Time O(log² n)Space O(1)
Subtract the largest shifted copy of the divisor (divisor << k) that still fits; add 2^k to the quotient. Handle signs and the INT_MIN edge case.
function divide(dividend, divisor) { const INT_MAX = 2 ** 31 - 1, INT_MIN = -(2 ** 31); if (dividend === INT_MIN && divisor === -1) return INT_MAX; const neg = (dividend < 0) !== (divisor < 0); let a = Math.abs(dividend), b = Math.abs(divisor), q = 0; while (a >= b) { let temp = b, multiple = 1; while (a >= (temp << 1)) { temp <<= 1; multiple <<= 1; } a -= temp; q += multiple; } return neg ? -q : q;}