29. 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, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

Note:

Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, assume that your function returns 231 − 1 when the division result overflows.

My Answer 1: Time Limit Exceeded (13 / 989 test cases passed.)

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == 0 or divisor == 1:
            return dividend
        if (dividend >= 2**31-1 and divisor == 1) or (dividend <= -2**31 and divisor == -1):
            return 2**31-1
        if (dividend >= 2**31-1 and divisor == -1) or (dividend <= -2**31 and divisor == 1):
            return -2**31
        
        isminus = 0
        count = 0
        if dividend < 0 and divisor < 0:
            isminus = 0
        elif dividend < 0:
            dividend *= -1
            isminus = 1
        elif divisor < 0:
            divisor *= -1
            isminus = 1
            
        while dividend:
            if dividend - divisor >= 0:
                count += 1
            else:
                break
            dividend -= divisor
        
        if isminus: count *= -1
        return count

곱셈, 나눗셈 사용이 안되면 뺄셈으로 계산해보려 했는데
2147483647 이딴 값이 케이스에 많아서 노답됐다...

Solution 1: Runtime: 40 ms - 16.11% / Memory Usage: 14 MB - 94.84%

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == 0 or divisor == 1: #not necessary but makes things simpler
            return dividend
        if dividend == -2**31 and divisor == -1: #accurately deal with overflow
            return 2**31-1
        neg = (dividend < 0) ^ (divisor < 0)
        dividend = abs(dividend)
        divisor = abs(divisor)
        endres = 0
        while dividend >= divisor:
		   #At each iteration subtract the largest possible divisor*r=divisor*(2**k)
            resm = divisor
            r = 1
            while resm + resm < dividend:
                r += r
                resm += resm
            dividend -= resm
            endres += r
        return 0 - endres if neg else endres

neg 로 둘 중 하나가 음수면 1이 되어 마지막에 endres 값에 -(마이너스)를 붙여준다.
dividend 와 divisor 는 절댓값으로 바꿔주고
while resm + resm < dividend: 에서는 divisor 의 n 배수만큼 돌리고 그 값을 dividend 에서 빼주는 듯