Easy understand Python Code O(log n)


  • 0
    class Solution(object):
        def divide(self, dividend, divisor):
            if divisor == 0:
                return -1
            if dividend == 0:
                return 0
            ans, level,  = 0,abs(divisor)
            flag = -1 if ((dividend > 0 and divisor < 0) or (dividend < 0 and divisor > 0)) else 1
             # this line can also write as flag = dividend ^ divisor , because we only need to know
             # if the ans is positive or not
            dic, table,dividend, divisor = {level:1},[level], abs(dividend), abs(divisor)
            for i in range(0,31):
                dic[level + level],level = dic[level] + dic[level],level + level
                table.append(level)
            while(dividend >= divisor):
                if level > dividend:
                    level = table[table.index(level) - 1]
                else:
                    dividend -= level
                    ans += dic[level]
            if (ans > 2147483648) or (ans == 2147483648 and flag > 0):  
             # can also use sys.maxsize as 2147483647
                return 2147483647
            return -ans if flag < 0 else ans
    

Log in to reply
 

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