## Divide Two Integers

• Time:O(\log^2 n)
• Space:O(1)

## C++

``````class Solution {
public:
int divide(int dividend, int divisor) {
// -2^{31} / -1 = 2^31 -> overflow so return 2^31 - 1
if (dividend == INT_MIN && divisor == -1)
return INT_MAX;

const int sign = dividend > 0 ^ divisor > 0 ? -1 : 1;
long ans = 0;
long dvd = labs(dividend);
long dvs = labs(divisor);

while (dvd >= dvs) {
long k = 1;
while (k * 2 * dvs <= dvd)
k *= 2;
dvd -= k * dvs;
ans += k;
}

return sign * ans;
}
};
``````

## JAVA

``````class Solution {
public int divide(long dividend, long divisor) {
// -2^{31} / -1 = 2^31 -> overflow so return 2^31 - 1
if (dividend == Integer.MIN_VALUE && divisor == -1)
return Integer.MAX_VALUE;

final int sign = dividend > 0 ^ divisor > 0 ? -1 : 1;
long ans = 0;
long dvd = Math.abs(dividend);
long dvs = Math.abs(divisor);

while (dvd >= dvs) {
long k = 1;
while (k * 2 * dvs <= dvd)
k *= 2;
dvd -= k * dvs;
ans += k;
}

return sign * (int) ans;
}
}
``````

## Python

``````class Solution:
def divide(self, dividend: int, divisor: int) -> int:
if dividend == -2**31 and divisor == -1:
return 2**31 - 1

sign = -1 if (dividend > 0) ^ (divisor > 0) else 1
ans = 0
dvd = abs(dividend)
dvs = abs(divisor)

while dvd >= dvs:
k = 1
while k * 2 * dvs <= dvd:
k <<= 1
dvd -= k * dvs
ans += k

return sign * ans
``````