Divide Two Integers

Problem

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, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

Note:

• Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, assume that your function returns 231 − 1 when the division result overflows.

Constraints:

• -231 <= dividend, divisor <= 231 - 1

• divisor != 0

For example:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2

Thought Process

• The naive approach here is to continuosuly subtract the divisor from the dividend until you are at a point where the dividend is smaller than the divisor. We would return the count of how many times we subtracted the divisor from the dividend and this would be our answer. However, this is costly because it runs in linear time.

• A better method is to subtract the divisor from the dividend in a more efficent way. We can subtract divisor, 2*divisor, 4*divisor, 8*divisor... and so on. Now the subtracting process only takes log-time.

• We need to also check that our divisor variable is never greater than our dividend and to reset the divisor variable if this happens

Solution

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        
        neg = (divisor < 0 and dividend > 0) or (divisor > 0 and dividend < 0)
        divisor, dividend = abs(divisor), abs(dividend)
        
        q = 0
        while divisor <= dividend:
            temp = divisor 
            numCount = 1
            while temp <= dividend:
                dividend-=temp 
                
                q += numCount
                
                temp<<= 1
                numCount <<= 1
          
                
        q = 0-q if neg else q
        
        return min(max(-2**31, q),2**31-1)

Time Complexity

• Time: O(log n)

• Space: O(1)