🎨Now live: Try our Free AI Image Generation Feature

Description
The problem is to implement a function that performs division of two integers without using multiplication, division, and mod operators. The result should be an integer. If the result overflows, it should return the maximum integer value possible.
Intuition
The problem can be approached by simulating the division process using subtraction. The key observation is that repeated subtraction can be optimized by doubling the divisor repeatedly, similar to how binary long division works. This allows us to subtract large chunks at a time, which speeds up the process.
Approach
- Handle the edge case where dividing
-2147483648
by-1
would result in an overflow. Return2147483647
in this case. - Check if either the dividend or divisor is negative to determine the sign of the result.
- Convert both the dividend and divisor to their absolute values.
- Use a loop to repeatedly subtract the divisor from the dividend while shifting the divisor left (multiplying by 2) each time to efficiently find the quotient.
- Adjust the quotient according to the sign determined earlier.
- Return the final quotient.
Complexity
Time Complexity:
O(log n), where n
is the absolute value of the dividend. The divisor is doubled in each iteration, which makes the operation logarithmic.
Space Complexity:
O(1), as only a few extra variables are used.
Code
C++
class Solution {
public:
int divide(int dividend, int divisor) {
if (dividend == INT_MIN && divisor == -1) return INT_MAX;
if (abs(divisor) == 1) return dividend * divisor;
bool isNegative = (dividend < 0) ^ (divisor < 0);
int count = 0;
long long absDividend = abs((long long)dividend);
long long absDivisor = abs((long long)divisor);
while (absDividend >= absDivisor) {
long long base = absDivisor;
int x = 1;
while (base <= (absDividend >> 1)) {
base <<= 1;
x <<= 1;
}
count += x;
absDividend -= base;
}
return isNegative ? -count : count;
}
};
Python
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
if dividend == -2147483648 and divisor == -1:
return 2147483647
if abs(divisor) == 1:
return dividend * divisor
is_negative = (dividend < 0) ^ (divisor < 0)
count = 0
dividend, divisor = abs(dividend), abs(divisor)
while dividend >= divisor:
x = 1
base = divisor
while base <= (dividend >> 1):
base <<= 1
x <<= 1
count += x
dividend -= base
return -count if is_negative else count
Java
class Solution {
public int divide(int dividend, int divisor) {
if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
if (Math.abs(divisor) == 1) return dividend * divisor;
boolean isNegative = (dividend < 0) ^ (divisor < 0);
int count = 0;
long absDividend = Math.abs((long)dividend);
long absDivisor = Math.abs((long)divisor);
while (absDividend >= absDivisor) {
long base = absDivisor;
int x = 1;
while (base <= (absDividend >> 1)) {
base <<= 1;
x <<= 1;
}
count += x;
absDividend -= base;
}
return isNegative ? -count : count;
}
}
JavaScript
var divide = function (dividend, divisor) {
if (dividend === -2147483648 && divisor === -1) return 2147483647
if (Math.abs(divisor) === 1) return dividend * divisor;
let isNegative = false;
let count = 0;
if ((dividend < 0 || divisor < 0) && !(dividend < 0 && divisor < 0))
isNegative = true;
dividend = Math.abs(dividend);
divisor = Math.abs(divisor);
while (dividend >= divisor) {
let x = 1;
base = divisor;
while (base <= (dividend >> 1)) {
base = base << 1;
x = x << 1;
}
count += x;
dividend -= base;
}
if (isNegative) return -count;
return count;
};