[LeetCode] 29. Divide Two Integers

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

Dividend / Divisor = Quotient + Remainder 

Quotient means how many 'Divisor' can be found in range of [0, Dividend]

Time Complexity :  O ( Log ( dividend ) )

Space Complexity : O ( 1 )

MAX_INT = 2 ** 31 - 1
MIN_INT = -2 ** 31
    
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == 0: return 0
        
        sign = -1 if (dividend > 0) ^ (divisor > 0) else 1
        
        if dividend == MIN_INT:
            if divisor == MIN_INT: return 1
            if divisor == -1: return MAX_INT
            
            divisor = abs(divisor)
            
            return sign * (1 + self.divide(abs(dividend + divisor), divisor))
        
        if divisor == MIN_INT: return 0
        
        if abs(divisor) == 1: return sign * abs(dividend)
        
        dividend = abs(dividend)
        divisor = abs(divisor)
        
        result = 0
        
        while divisor <= dividend:
            tmp = divisor
            count = 1
            while tmp << 1 <= dividend:
                count <<= 1
                tmp <<= 1
            
            dividend -= tmp
            result += count
        
        return sign * result

Edited on 02/27/2021. Process edge case when dividend == MIN_INT.