LeetCode-Py/LeetCode/_0001_0050/_029_DivideTwoIntegers.py at master · BigEggStudy/LeetCode-Py · GitHub

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
34
#-----------------------------------------------------------------------------
# Runtime: 32ms
# Memory Usage:
# Link:
#-----------------------------------------------------------------------------

INT_MAX = 2 ** 31 - 1

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == 0 or divisor == 1:
            return dividend
        if divisor == -1:
            return -dividend if -dividend < INT_MAX else INT_MAX

        sign = 1
        if (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0):
            sign = -1
        dividend, divisor = abs(dividend), abs(divisor)
        result = 0
        step_divisor = divisor
        step_result = 1
        while dividend >= step_divisor + step_divisor:
            step_divisor += step_divisor
            step_result += step_result

        while dividend >= divisor:
            if dividend >= step_divisor:
                dividend -= step_divisor
                result += step_result
            step_divisor = (step_divisor >> 1)
            step_result = (step_result >> 1)

        return sign * result