Divide two integers

Problem Link

29. Divide Two Integers – LeetCode

Problem Statement

Given two integers dividend and divisor, divide two integers without using multiplication, division, or mod operator.

Return the quotient after dividing dividend by divisor.

Note:

• If the division result overflows (i.e., exceeds the 32-bit signed integer range), return 2³¹ − 1.

• Truncate the result toward zero (i.e., like integer division in C or Java).

Examples

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10 / 3 = 3.333..., truncated to 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7 / -3 = -2.333..., truncated to -2

Example 3:

Input: dividend = -2147483648, divisor = -1
Output: 2147483647
Explanation: Prevents overflow of 32-bit signed int

Constraints

• -2³¹ <= dividend, divisor <= 2³¹ - 1

• divisor != 0

Intuition

We can’t use the standard operators, so we simulate division via repeated subtraction, but to do it efficiently, we use:

• Bitwise left shifts to double the divisor

• Subtract the largest multiple of divisor possible from the dividend

• Repeat the process while updating the quotient

This mimics long division in binary, optimizing the process to logarithmic steps.

Approach: Bitwise Long Division (Doubling Strategy)

1. Handle the edge case of overflow:

   • INT_MIN / -1 exceeds 32-bit signed range → return Integer.MAX_VALUE

2. Use ^ (XOR) to check if the result should be negative:

   • Result is negative if only one of the operands is negative

3. Convert both dividend and divisor to long and take absolute values to avoid overflow and simplify logic

4. Repeatedly subtract the largest shifted divisor from the current dividend:

   • Find the maximum temp = divisor * 2^k such that temp <= dividend

   • Subtract temp from dividend

   • Add 2^k to the result (cnt)

5. Return result with proper sign

Java Code

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

        // Determine if result is negative
        boolean neg = (dividend < 0) ^ (divisor < 0);

        // Convert to long and take absolute values
        long n = Math.abs((long) dividend);
        long d = Math.abs((long) divisor);
        int cnt = 0;

        // Subtract largest multiple of divisor from dividend
        while (n >= d) {
            long num = 1, temp = d;
            while (n >= (temp << 1)) {
                temp <<= 1;
                num <<= 1;
            }
            n -= temp;
            cnt += num;
        }

        return neg ? -cnt : cnt;
    }
}

Time and Space Complexity

Dry Run

Input: dividend = 43, divisor = 3

• n = 43, d = 3

• First round:

  • temp = 3 → 6 → 12 → 24 → stop (next would be 48)

  • Subtract 24 → n = 19, cnt = 8

• Second round:

  • temp = 3 → 6 → 12 → stop (next would be 24)

  • Subtract 12 → n = 7, cnt = 12

• Third round:

  • temp = 3 → 6 → stop

  • Subtract 6 → n = 1, cnt = 14

• Done (1 < 3)

Output: 14

Conclusion

This problem is a classic example of bitwise optimization for arithmetic simulation. It's a frequent interview question used to assess:

• Bit manipulation proficiency

• Handling edge cases like overflow

• Optimization using binary search principles