29.md

29. Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

my thoughts:

1. use plaint +/-. Time limit exceed when test -2147483648 / -1.

2. double divisor each time, use plaint +/- to handle the remaining. TLE when test 2147483647/1.

3. double divisor each time, implicitly use division rules for remaining, re. * cheated using re+re+... 10 times other than 10*re.

my solution:

**********56ms
class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if divisor == 0:
            return
        if dividend == 0:
            return 0
        
        sign = -1
        if (divisor < 0 and dividend < 0) or (divisor > 0 and dividend > 0):
            sign = 1
        
        dd = abs(dividend)
        dr = abs(divisor)
        res = 0
        if dd>=dr:
            dd -= dr
            res += 1
        else:
            return 0
        t = dr
        while dd >= t:                
            res += res
            dd -= t
            t += t
        if dd>=dr:
            r2 = []
            sdd = str(dd)
            sdr = str(dr)
            i = len(sdr)
            cdd = int(sdd[:i])
            carrier = 0
            while i<=len(sdd):
                t = 0
                cdd += carrier
                while cdd>= dr:
                    cdd -= dr
                    t += 1
                r2.append(t)
                carrier = cdd+cdd+cdd+cdd+cdd+cdd+cdd+cdd+cdd+cdd
                if i<len(sdd):
                    cdd = int(sdd[i])
                i += 1
            res2 = [str(x) for x in r2]
            r = ''.join(res2)
            res += int(r)
        res *= sign    
        if res>2147483647:
            return 2147483647
        if res<-2147483648:
            return -2147483648
        return res

my comments:

from other ppl's solution:

1. double divisor all the way, 45ms:
class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        ans, total, sign = 0, 0, 1
        if dividend < 0:
            dividend *= -1
            sign *= -1
        if divisor < 0:
            divisor *= -1
            sign *= -1
        while divisor <= dividend:
            total = divisor
            count = 1
            while total + total <= dividend:
                total += total
                count += count
            dividend -= total
            ans += count
        ans *= sign
        return min(max(-2147483648, ans), 2147483647)