Skip to main content

29. Divide Two Integers

https://leetcode.com/problems/divide-two-integers/

Python​

Minus divisor one-by-one (Timelimit Exceed)​

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # Edge case, 32bit INT did not have 2147483648
        if dividend == -2147483648 and divisor == -1:
            return 2147483647

        # Decide the sign of the answer
        is_negative = False

        if dividend < 0:
            dividend = -dividend
            is_negative = True

        if divisor < 0:
            divisor = -divisor
            is_negative = False if is_negative else True

        ans = 0
        while dividend >= divisor:
            ans += 1
            dividend -= divisor

        return -ans if is_negative else ans

Minus divisor on exponentially grow while fit​

  • 除數(divisor)在允許範圍內(還可以讓被除數減的時候)，讓他程指數增長(二次方)
  • 類似TCP/IP congestion control時的AIMD
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == -2147483648 and divisor == -1:
            return 2147483647

        is_negative = (dividend < 0) ^ (divisor < 0)
        dividend, divisor = abs(dividend), abs(divisor)

        ans = 0
        while dividend >= divisor:
            power_divisor, power = divisor, 1
            while dividend >= power_divisor:
                dividend -= power_divisor
                ans += power
                power <<= 1
                power_divisor <<= 1

        return -ans if is_negative else ans