O(logN) Python solution


  • 1
    S

    Several of the most voted solutions have O((logN)^2) time complexity. Here I provide a faster (O(logN)) solution with the cost of O(logN) space. The idea is to store all the left shifted divisors that are less than the dividend in a list (array).

    def divide(self, dividend, divisor):
            """
            :type dividend: int
            :type divisor: int
            :rtype: int
            """
            MAX_INT = 2147483647 #python 3 have removed this constant
            MIN_INT = -2147483648
            if (divisor == 0) or (divisor == -1 and dividend == MIN_INT):
                return MAX_INT #two possible cases of overflow
            vals = []
            if ((dividend > 0) and (divisor > 0)) or ((dividend < 0) and (divisor < 0)):
                sign = 1
            else:
                sign = -1
            dividend = abs(dividend)
            divisor = abs(divisor)
            while dividend >= divisor:
                vals.append(divisor)
                divisor += divisor
            result = 0
            for i in range(len(vals) - 1, -1, -1):
                if dividend >= vals[i]:
                    dividend -= vals[i]
                    result += 2**i
            return result * sign
    

  • 0
    V

    Isn't this O(n) time complexity and O(n) space complexity? By the way, why is 'result += 2**i' ?


  • 0
    S

    This is O(logN) because in the while loop I double divisor each time:

    divisor += divisor
    

    Also because I double divisor every time, the values stored in "vals" are the exponentials.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.