LeetCode Solutions Blog

Divide Two Integers

Number: 29

Difficulty: Medium

Paid? No

Problem Description

Given two integers dividend and divisor, compute the quotient after dividing dividend by divisor without using multiplication, division, or modulo operations. The quotient should be truncated toward zero and must be clamped to a 32-bit signed integer range.

Key Insights

Handle sign differences between dividend and divisor.
Convert both numbers to negatives to avoid overflow issues (since -2^31 has no positive counterpart).
Use bit shifting (doubling) to subtract large chunks from the dividend, implementing a form of binary search.
Carefully manage the 32-bit integer boundary conditions.

Space and Time Complexity

Time Complexity: O(log n), where n is the absolute value of the dividend. Space Complexity: O(1), using a constant amount of space.

Solution

The idea is to simulate division using subtraction and bit shifts. First, we determine if the result should be negative based on the input signs. To avoid edge case issues (like -2^31), we work with negatives. Using bit shifting, we find the maximum multiple of the divisor that can be subtracted from the dividend, subtract it, and add the corresponding shift-based multiplier to the quotient. Finally, we ensure the quotient stays within the 32-bit signed integer range. This method efficiently reduces the dividend in logarithmic steps.

Code Solutions

# Python solution with line-by-line comments

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # Define constants for integer limits
        INT_MAX = 2**31 - 1
        INT_MIN = -2**31
        
        # Special case: overflow condition
        if dividend == INT_MIN and divisor == -1:
            return INT_MAX
        
        # Determine the sign of the quotient
        negative = (dividend < 0) != (divisor < 0)
        
        # Convert both dividend and divisor to negative to avoid overflow
        dividend_neg = -dividend if dividend > 0 else dividend
        divisor_neg = -divisor if divisor > 0 else divisor
        
        quotient = 0
        # Begin subtracting multiples of divisor_neg from dividend_neg
        while dividend_neg <= divisor_neg:
            temp_divisor = divisor_neg
            multiple = 1
            
            # Double the divisor until it is less than or equal to the dividend_neg
            while dividend_neg <= (temp_divisor << 1) and (temp_divisor << 1) < 0:
                temp_divisor <<= 1
                multiple <<= 1
            
            # Subtract the found multiple from the dividend_neg
            dividend_neg -= temp_divisor
            quotient += multiple
        
        # Adjust quotient sign
        return -quotient if negative else quotient

# Example usage:
# sol = Solution()
# print(sol.divide(10, 3))  # Output: 3