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.

 1 class 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:

 1 class 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 
25 print(Solution().divide(2147483647, 1))