Divide Two Integers-Leetcode 29 Solution

The “Divide Two Integers“ problem on LeetCode challenges you to implement division between two integers without using multiplication, division, or modulus operators. The task also requires handling edge cases, such as overflow and truncation towards zero.

This blog will cover all approaches, from naive to optimal, with Java implementations.

Problem Description for Divide Two Integers

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: [−231, 231 − 1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -231.

Approaches

1. Naive Subtraction-Based Approach

This approach repeatedly subtracts the divisor from the dividend while counting how many subtractions are performed.

Algorithm:

1. Take the absolute values of dividend and divisor.
2. Perform repeated subtraction.
3. Adjust the sign of the result based on the inputs.

Code:

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        if (dividend == Integer.MIN_VALUE && divisor == 1) return Integer.MIN_VALUE;

        int absDividend = Math.abs(dividend);
        int absDivisor = Math.abs(divisor);
        int result = 0;

        while (absDividend - absDivisor >= 0) {
            absDividend -= absDivisor;
            result++;
        }

        return (dividend > 0) == (divisor > 0) ? result : -result;
    }
}

Complexity:

• Time: O(N), where N is the dividend.
• Space: O(1).

2. Optimized Approach Using Bit Manipulation

Instead of subtracting repeatedly, this method uses bitwise shifts to subtract multiples of the divisor in powers of two.

Algorithm:

1. Use shifts (<<) to scale the divisor until it exceeds the dividend.
2. Subtract scaled values and count the multiples.
3. Handle signs and edge cases.

Code:

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;

        long absDividend = Math.abs((long) dividend);
        long absDivisor = Math.abs((long) divisor);
        int result = 0;

        while (absDividend >= absDivisor) {
            long tempDivisor = absDivisor, multiple = 1;
            while (absDividend >= (tempDivisor << 1)) {
                tempDivisor <<= 1;
                multiple <<= 1;
            }
            absDividend -= tempDivisor;
            result += multiple;
        }

        return (dividend > 0) == (divisor > 0) ? result : -result;
    }
}

Complexity:

• Time: O(log⁡N), where N is the dividend.
• Space: O(1).

3. Handling Overflow and Edge Cases

The key edge cases to consider are:

1. Overflow: Integer.MIN_VALUE / -1 causes overflow, returning Integer.MAX_VALUE.
2. Sign Handling: Use XOR to determine if the result is negative.

Comparison of Approaches for Divide Two Integers

Conclusion

The bit manipulation approach is the most efficient and handles edge cases well. Always check for overflow and input constraints when implementing.