Share my pthon code with binary search,easy to understand


  • 0
    class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        #solution1- binary search
        ncount,flag,res=0,1,0
        if (divisor<0 and dividend>0) or (divisor>0 and dividend<0):
            flag=-1
        divisor,dividend=abs(divisor),abs(dividend)
        if divisor>dividend:return 0
        while dividend>=divisor:
            tmp=divisor
            ncount=1
            while tmp<=dividend:
                dividend-=tmp
                res+=ncount
                tmp+=tmp
                ncount+=ncount
        #consider the overflow, even though python3 didn't consider
        if res*flag<-2147483648:return -2147483648
        elif res*flag>2147483647:return 2147483647
        else: return res*flag
    

    considering we can't use multiplication, division and mod operator. So I can use the add and abstract, while it's too computational if we subtract the divisor one by one, then we use the variant binary search to do the question. At the end, we need to consider the overflow of MAX_INT.


Log in to reply
 

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