(Medium #29) Divide Two Integers
Problem
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.
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
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: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.
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.
Example 1:
Input: dividend = 10, divisor = 3 Output: 3
Example 2:
Input: dividend = 7, divisor = -3 Output: -2
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: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.
My solution
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
MAXNUM = 2**31-1
MINNUM = -2**31
if dividend == 0:
return 0
if (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0):
sign = 1
else:
sign = -1
dividend = abs(dividend)
divisor = abs(divisor)
if dividend < divisor:
return 0
divisor2 = divisor
result = 0
term = 1
# print("1", dividend, divisor, divisor2, result)
while True:
if dividend < divisor2:
break
dividend -= divisor2
result += term
divisor2 += divisor2
term += term
# print("2", dividend, divisor, divisor2, result)
result += self.divide(dividend, divisor)
if sign*result > MAXNUM:
return MAXNUM
elif sign*result < MINNUM:
return MINNUM
else:
return sign*result
Runtime: 44ms, Memory: 13.9MB
def divide(self, dividend: int, divisor: int) -> int:
MAXNUM = 2**31-1
MINNUM = -2**31
if dividend == 0:
return 0
if (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0):
sign = 1
else:
sign = -1
dividend = abs(dividend)
divisor = abs(divisor)
if dividend < divisor:
return 0
divisor2 = divisor
result = 0
term = 1
# print("1", dividend, divisor, divisor2, result)
while True:
if dividend < divisor2:
break
dividend -= divisor2
result += term
divisor2 += divisor2
term += term
# print("2", dividend, divisor, divisor2, result)
result += self.divide(dividend, divisor)
if sign*result > MAXNUM:
return MAXNUM
elif sign*result < MINNUM:
return MINNUM
else:
return sign*result
댓글
댓글 쓰기