Python Solution with dict to record O(log(N)) Solution


  • 0
    T
    class Solution(object):
        def divide(self, divisor, dividend):
            """
            :type dividend: int
            :type divisor: int
            :rtype: int
            """
            if divisor == -2147483648 and dividend == -1:
                return 2147483647
            if dividend == 1:
                return divisor
            if dividend == -1:
                return -divisor
            if dividend > 0 and divisor > 0 or dividend < 0 and divisor < 0:
                sign = 1
            else:
                sign = -1
            dividend = abs(dividend)
            divisor = abs(divisor)
            dic = {1: dividend}
            k = 1
            while dividend < divisor:
                k += k
                dividend += dividend
                dic[k] = dividend
            data = [(k, dic[k]) for k in sorted(dic.keys(),reverse=True)]
            res = 0
            tmp = 0
            for d in data:
                if tmp + d[1] < divisor:
                    tmp += d[1]
                    res += d[0]
                if tmp + d[1] == divisor:
                    return (res + d[0]) * sign
                else:
                    continue
            return sign * res
    

Log in to reply
 

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