Dare2Solve
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.
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.
-2147483648
by -1
would result in an overflow. Return 2147483647
in this case.O(log n), where n
is the absolute value of the dividend. The divisor is doubled in each iteration, which makes the operation logarithmic.
O(1), as only a few extra variables are used.
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;
}
};
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
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;
}
}
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;
};