Divide Two Integers

Difficulty: Medium | Acceptance: 19.70% | Paid: No

Topics: Math, Bit Manipulation

Given two integers ‘dividend’ and ‘divisor’, divide two integers without using multiplication, division, and mod operator. The integer division should truncate toward zero, which means losing its fractional part. For example, ‘8.345’ would be truncated to ‘8’, and ‘-2.7335’ would be truncated to ‘-2’. Return the quotient after dividing ‘dividend’ by ‘divisor’. Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2³¹, 2³¹ − 1]. For this problem, if the quotient is strictly greater than 2³¹ − 1, return 2³¹ − 1, and if the quotient is strictly less than −2³¹, return −2³¹.

• Examples
• Constraints
• Brute Force (Linear Subtraction)
• Exponential Search (Doubling)
• Bitwise Long Division

Examples

Input

dividend = 10, divisor = 3

Output

3

Explanation

10/3 = 3.33333… which is truncated to 3.

Input

dividend = 7, divisor = -3

Output

-2

Explanation

7/-3 = -2.33333… which is truncated to -2.

Constraints

- -2³¹ <= dividend, divisor <= 2³¹ - 1
- divisor != 0

Brute Force (Linear Subtraction)

Intuition

The most basic way to divide is to repeatedly subtract the divisor from the dividend until the remainder is less than the divisor.

Steps

• Handle the edge case where dividend is -2³¹ and divisor is -1, which would result in 2³¹ (overflow).
• Determine the sign of the quotient based on whether the signs of the dividend and divisor match.
• Convert both numbers to their absolute values. To avoid overflow with -2³¹, work with negative numbers or 64-bit integers.
• Subtract the divisor from the dividend repeatedly, incrementing a counter each time.
• Apply the sign to the counter and return the result.

class Solution:
    def divide(self, dividend, divisor):
        if dividend == -2147483648 and divisor == -1:
            return 2147483647
        
        negative = (dividend < 0) != (divisor < 0)
        dividend, divisor = abs(dividend), abs(divisor)
        
        quotient = 0
        while dividend >= divisor:
            dividend -= divisor
            quotient += 1
            
        return -quotient if negative else quotient

Complexity

• Time: O(N) where N is the dividend. In the worst case (e.g., 2³¹ / 1), this will perform over 2 billion subtractions, leading to Time Limit Exceeded.
• Space: O(1) as we only use a few variables.
• Notes: This approach is too slow for the given constraints but serves as a baseline.

Exponential Search (Doubling)

Intuition

Instead of subtracting the divisor once, we can subtract multiples of the divisor (divisor * 2, divisor * 4, divisor * 8…) to reach the quotient faster.

Steps

• Handle the overflow case: dividend = -2³¹, divisor = -1.
• Determine the sign of the result.
• Convert both dividend and divisor to negative numbers. We use negative numbers because the range of negative integers [-2³¹] is larger than positive integers [2³¹-1].
• While the dividend is less than or equal to the divisor (both are negative):
• Find the largest power of 2 multiple of the divisor such that (divisor * 2ᵏ) >= dividend.
• Subtract this multiple from the dividend and add 2ᵏ to the quotient.
• Repeat until the dividend is greater than the divisor.

class Solution:
    def divide(self, dividend, divisor):
        if dividend == -2147483648 and divisor == -1:
            return 2147483647
        
        negative = (dividend < 0) != (divisor < 0)
        dividend = -abs(dividend)
        divisor = -abs(divisor)
        
        quotient = 0
        while dividend <= divisor:
            temp = divisor
            multiple = 1
            while temp >= -1073741824 and dividend <= (temp + temp):
                temp += temp
                multiple += multiple
            
            dividend -= temp
            quotient += multiple
            
        return -quotient if negative else quotient

Complexity

• Time: O(log² N) where N is the dividend. The outer loop runs until the dividend is exhausted, and the inner loop doubles the divisor until it exceeds the current dividend. Each inner loop reduces the dividend by at least half of the remaining amount.
• Space: O(1) as we only use a constant amount of extra space.
• Notes: This is a significant improvement over linear subtraction and fits within the time limits.

Bitwise Long Division

Intuition

This approach mimics the manual long division process but in binary. We iterate through the bits of the dividend from most significant to least significant.

Steps

• Handle the overflow case: dividend = -2³¹, divisor = -1.
• Determine the sign of the result.
• Convert both numbers to positive 64-bit integers (long) to simplify bit shifting and avoid overflow issues with -2³¹.
• Iterate from bit 31 down to 0.
• Check if (divisor << i) is less than or equal to the current dividend.
• If it is, subtract (divisor << i) from the dividend and set the i-th bit of the quotient.
• Return the quotient with the correct sign, ensuring it stays within the 32-bit signed integer range.

class Solution:
    def divide(self, dividend, divisor):
        if dividend == -2147483648 and divisor == -1:
            return 2147483647
        
        negative = (dividend < 0) != (divisor < 0)
        a, b = abs(dividend), abs(divisor)
        
        quotient = 0
        for i in range(31, -1, -1):
            if (a >> i) >= b:
                quotient += (1 << i)
                a -= (b << i)
        
        return -quotient if negative else quotient

Complexity

• Time: O(log N) where N is the dividend. Specifically, it is O(W) where W is the number of bits in the integer (32 in this case).
• Space: O(1) as we only use a few variables.
• Notes: This is the most efficient approach and is essentially how hardware-level division is often implemented.