Divide two integers without *, / or %

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}