Leetcode

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