Fast and simple Python solutions (56ms - 64ms). No Bitwise Operators.


  • 9
    C

    idea:
    keep subtracting the new divisor div from the remaining left and then doubling div (by div += div). if left < div, start from the original divisor. Do these until left < divisor.


    def divide(self, dividend, divisor):     
        neg=( (dividend < 0) != (divisor < 0) )
        dividend = left = abs(dividend)
        divisor  = div  = abs(divisor)
        Q = 1
        ans = 0
        while left >= divisor:
            left -= div
            ans  += Q 
            Q    += Q
            div  += div
            if left < div:
                div = divisor
                Q = 1
        if neg:
            return max(-ans, -2147483648)
        else:
            return min(ans, 2147483647)
    

    Recursive version:

    def divide(self, dividend, divisor):  
        neg=( (dividend < 0) != (divisor < 0) )
        dividend = left = abs(dividend)
        divisor  = div  = abs(divisor)       
        if dividend < divisor:
            return 0
        Q = 1
        ans = 0
        while left >= div:
            left -= div
            ans  += Q
            Q    += Q
            div  += div
        if neg:
            return max(-(ans + self.divide(left, divisor)), -2147483648)
        else:
            return min(ans + self.divide(left, divisor), 2147483647)

  • 0
    A

    inspired by yours

    def divide(self, dividend, divisor):
        neg = False
        if dividend < 0:
            neg = not neg
            dividend = -dividend
        if divisor < 0:
            neg = not neg
            divisor = -divisor
            
        ans = 0
        div = divisor
        mul = 1 # multiple times
        while dividend >= divisor:
            if dividend >= div:
                dividend -= div
                ans += mul
                div = div << 1
                mul = mul << 1
            else:
                div = div >> 1
                mul = mul >> 1
                if dividend < div:
                    continue
                dividend -= div
                ans += mul
        
        if neg:
            return max(-ans, -2147483648)
        return min(2147483647, ans)

  • 0
    S

    really elegant and clear


  • 0
    T

    Clean and fast. Easy to understand. Thank you.


  • 0

    Just realize that Q += Q is much faster than Q << 1. Thank you !


Log in to reply
 

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