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
