divide two integers
This is probably one of my favourite questions. My latest code. Still takes me about half an hour to crank this out. Next time should take less than 5 minutes.
Beats 99%
Runtime: 20 ms, faster than 99.90% of Python3 online submissions for Divide Two Integers.
Memory Usage: 13.7 MB, less than 80.96% of Python3 online submissions for Divide Two Integers.
1class Solution:
2 def divide(self, a: int, b: int) -> int:
3 sign = -1 if (a < 0) ^ (b < 0) else 1
4 a, b = -a if a < 0 else a, -b if b < 0 else b
5 power, res = 32, 0
6 while a >= b:
7 while (b << power) > a:
8 power -= 1
9 res += 1 << power
10 a -= b << power
11 res = min(res, 2 ** 31 - (1 if sign == 1 else 0))
12 return res * sign
My previous attempt:
1class Solution:
2 def divide(self, a, b):
3
4 m = -1 if (a < 0) ^ (b < 0) else 1
5 a = -a if a < 0 else a
6 b = -b if b < 0 else b
7
8 k, r = 32, 0
9 while a > b:
10 while b << k > a:
11 k -= 1
12 r += 1 << k
13 a -= b << k
14
15 r = 1 * m if (a == b and r == 0) else r * m
16
17 if r < -2 << 30:
18 return 2 << 30
19 if r > 2 << 30 - 1:
20 return (2 << 30) - 1
21
22 return r
23
24
25print(Solution().divide(2147483647, 1))