Archived

divide two integers

An old note — I haven't updated it since I wrote it.

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))