algoadvance

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.

Note:

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Example 3:

Input: dividend = 0, divisor = 1
Output: 0

Example 4:

Input: dividend = 1, divisor = 1
Output: 1

Clarifying Questions

  1. Should any special cases be considered apart from integer overflow and dividing by zero?
  2. How do we handle division by zero, if applicable in our problem scope?
  3. Is there a specific way to handle negative number input?

Strategy

We use bit manipulation to perform the division iteratively, essentially by subtracting the divisor shifted left by certain amounts until the dividend is reduced below the divisor. This mimics the process of long division.

  1. Sign Determination: Determine the sign of the result based on the signs of the dividend and divisor.
  2. Edge Cases: Handle overflow and underflow.
  3. Bitwise Division: Using bit shifting and subtraction to compute the quotient without using direct division.

Code

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # Handle edge cases
        if divisor == 0:
            raise ValueError("Divisor cannot be zero.")
        
        if dividend == -2**31 and divisor == -1:
            return 2**31 - 1
        
        # Determine the sign of the result
        negative = (dividend < 0) != (divisor < 0)
        
        # Work with positive numbers
        dividend, divisor = abs(dividend), abs(divisor)
        
        result = 0
        
        # Subtract divisor multiplicatively
        while dividend >= divisor:
            temp, multiple = divisor, 1
            while dividend >= (temp << 1):
                temp <<= 1
                multiple <<= 1
            dividend -= temp
            result += multiple
        
        if negative:
            result = -result
        
        # Ensure result is within the 32-bit integer bounds
        return max(-2**31, min(result, 2**31 - 1))

# Example usage
sol = Solution()
print(sol.divide(10, 3))  # Output: 3
print(sol.divide(7, -3))  # Output: -2
print(sol.divide(0, 1))  # Output: 0
print(sol.divide(1, 1))  # Output: 1

Time Complexity

The time complexity of this approach is O(log N), where N is the dividend. This is due to the repeated doubling (left shifts) of the divisor. Each doubling operation reduces the problem size significantly, making this algorithm efficient.

The space complexity is O(1) since we are only using a constant amount of extra space.

Try our interview co-pilot at AlgoAdvance.com