We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Divide Two Integers

Difficulty: Medium

Problem Description

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator. The integer division should truncate toward zero. Return the quotient after dividing dividend by divisor.

Key Insights

  • Division can be approached using repeated subtraction.
  • The algorithm must handle negative numbers and ensure the result truncates toward zero.
  • Bit manipulation can be utilized to speed up the subtraction process.
  • Boundary conditions must be considered to avoid integer overflow.

Space and Time Complexity

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

Solution

The solution leverages bit manipulation to efficiently compute the quotient. The algorithm repeatedly subtracts the divisor from the dividend while doubling the divisor using bit shifts. This allows us to count how many times the divisor fits into the dividend without exceeding it. The sign of the result is determined based on the signs of the dividend and divisor. Finally, we ensure that the result falls within the 32-bit signed integer range.

Code Solutions

def divide(dividend: int, divisor: int) -> int:
    # Handle overflow cases
    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 values
    dividend, divisor = abs(dividend), abs(divisor)
    
    quotient = 0
    # Bit manipulation to calculate quotient
    while dividend >= divisor:
        temp, multiple = divisor, 1
        while dividend >= (temp << 1):  # Double the divisor
            temp <<= 1
            multiple <<= 1
        dividend -= temp
        quotient += multiple
    
    # Apply the sign
    return -quotient if negative else quotient
← Back to All Questions