# 29. Divide Two Integers

• Time: $O(\log^2 n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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