https://leetcode.com/problems/divide-two-integers

I do not really like these type of problems, where you restricted in using operations. What we can use if we can not use multiplications and divisions: we can use only addition and subtraction. Let consider an example: 100 // 7

We can try just to subtract 7 while it is possible. However potentially it can be quite long, if dividend is big and divisor is small. Let us multiply 7 by 2 (in fact it is not multiplication, but addition with itself), until we are smaller than 100. 7 -> 14 -> 28 -> 56. Ans subtract 56 now, so we have 8 as result and we need to divide 44 by 7 now. Repeat procedure, so we subtract 28, and we have 8 + 4 as result and 44 - 28 = 16 = 2. Finally, we subtract 14 and we have 8 + 4 + 2 = 14 as result.

Let us precalculate pairs (7, 1), (14, 2), (28, 4), (56, 8). Then we iterate through these pairs in opposite direction and if we can subtract corresponding number, we subtract, if not - we go to the next one. Also we need to deal with signs and overflows here.

Complexity: time complexity is O(log n), where n = divident/divisor: there will be O(log n) terms in our cand list as well as this is limit for number of steps. Space complexity is O(log n) as well. What I mean by honest here, that a lot of people here in discussion either use some tricks which are not allowed, or complexity is wrong.

class Solution:
    def divide(self, dividend, divisor):
        if dividend == -1<<31 and divisor == -1: return (1<<31)-1

        a, b = abs(dividend), abs(divisor)
        sign = (dividend < 0) == (divisor < 0)
        res, cand = 0, [(1, b)]
        
        while b << 1 <= a:
            cand += [(cand[-1][0]<<1, b<<1)]
            b <<= 1
            
        for pw, num in cand[::-1]:
            if a >= num:
                a, res = a - num, res + pw
                
        return res if sign else -res

If you like the solution, you can upvote it on leetcode discussion section: Problem 0029