LeetCode_Divide Two Integers

Posted on | In | Views:

Divide Two Integers

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.
（非乘 除 取模 方法实现除法）

Note:

  • Both dividend and divisor will be 32-bit signed integers.
  • The divisor will never be 0.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 2^31 − 1 when the division result overflows.

Example:



1. 减法实现除法

这个题目很直观的就是将被除数不断地减去除数得到最终的商，但是会存在 Time Limit Exceeded 的问题。 因此需要在过程中不断地加大除数来加快得到最终结果。其中存在溢出的情况为被除数为-2^31, 除数为-1，得到的商为2^31，因此需要单独考虑。具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        if (dividend < 0 and divisor < 0) or (dividend > 0 and divisor > 0):
            flag = 1
        else:
            flag = -1
        
        dividend = abs(dividend)
        divisor = abs(divisor)
        
        re = 0
        i = 1
        new_divisor = divisor
        while dividend >= new_divisor:
            re += i
            dividend -= new_divisor
            
            new_divisor += new_divisor
            i += i
            if dividend < new_divisor:
                new_divisor = divisor
                i = 1
         
        if flag < 0:
            return -re
        else:
            MAX = pow(2, 31) - 1
            return min(re, MAX)