LeetCode 29 — Divide Two Integers(两数相除)

Question

    Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

    Return the quotient after dividing dividend by divisor.

    The integer division should truncate toward zero.

    E.g 1:
    Input: dividend = 10, divisor = 3
    Output: 3

    E.g 2:
    Input: dividend = 7, divisor = -3
    Output: -2

Solution

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if abs(dividend) < abs(divisor):
            return 0

        positive = (dividend < 0) is (divisor < 0)
        # abs value
        dividend_abs = abs(dividend)
        divisor_abs = abs(divisor)
        
        res = 0
        
           
        dividend = abs(dividend)
        divisor = abs(divisor)
        
        cur_dev = 0
        
        """
        If inner loop runs for say x times, then D gets doubled x times so that     
        D*2^x > N => x > log(N/D)  => O(log(N/D))
        And about outer loop
        N = 2^x * D + M   => such that N > M > D
        So next time inner loop will run for log(M/D)
        So its basically
        log(N/D) + log(M/D) + log(L/D) + ..... + log(D/D)   => log(N/D) * Y  
        """

        while dividend_abs >= divisor_abs:
            temp, index = divisor_abs, 1
            while dividend_abs >= temp:
                dividend_abs -= temp
                res += index
                index <<= 1
                temp <<= 1

        if not positive:
            res = -res
        
        if res < -2147483648:
            return -2147483648
        if res > 2147483647:
            return 2147483647        
        return res
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 在年初 心灵遭受了场磨难 余波至今未灭 那时候 睡着觉 做着梦 不小心醒了 还能为了续梦 继续睡下 梦境 随心所欲...
    骨头不疼啊阅读 126评论 0 0
  • It's Saturday. Chapter 7: The Patient During the night Ra...
    Mr_Oldman阅读 375评论 0 0
  • 有的人,你对他没有好感,你不会和对方说,但你会疏远他,不想和他说话。 好感的本质是一种情绪,情绪是一种生产力。情绪...
    新真我阅读 420评论 0 2
  • 去年大约这个时候,忽然发烧,大约两天一夜,到了40度,心里不停地做好像分支、循环的运算,一点不能安静。退烧之后又歇...
    潘琰阅读 61评论 0 0
  • 选秀之前,就算是经验丰富的老油条也很难为新秀寻找到最为准确模板。模板确立往往是在夏季联赛后才能得到最为准确的结果。...
    zoneball阅读 177评论 0 0