Divide Two Integers

Divide Two Integers – LeetCode Solution

This problem asks us to divide two integers without using multiplication (*), division (/), or modulo (%) operators.

We need to:

• Return the quotient only
• Remove decimal values (truncate toward zero)
• Handle overflow conditions for 32-bit integers

  

---

Approach

Instead of normal division, we use:

• Bit Manipulation
• Repeated Subtraction using Left Shift

Main Idea

• Convert both numbers into positive values
• Repeatedly subtract the divisor from dividend
• Use left shift (<<) to speed up subtraction
• Apply the sign at the end

---

Important Overflow Condition

If:

dividend = -2147483648
divisor = -1

Result becomes:

2147483648

But maximum 32-bit signed integer is:

2147483647

So return:

2147483647

---

Python Code (LeetCode)

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:

        # Handle overflow case
        if dividend == -2147483648 and divisor == -1:
            return 2147483647

        # Determine sign
        negative = (dividend < 0) != (divisor < 0)

        # Convert to positive
        dividend = abs(dividend)
        divisor = abs(divisor)

        quotient = 0

        # Division using bit manipulation
        while dividend >= divisor:

            temp = divisor
            multiple = 1

            while dividend >= (temp << 1):
                temp <<= 1
                multiple <<= 1

            dividend -= temp
            quotient += multiple

        # Apply sign
        if negative:
            quotient = -quotient

        return quotient

---

Example Walkthrough

Input

dividend = 10
divisor = 3

Process

10 - 6 = 4
4 - 3 = 1

Quotient becomes:

3

Output

3

---

Another Example

Input

dividend = 7
divisor = -3

Calculation

7 / -3 = -2.333

After truncating:

-2

Output

-2

---

Time Complexity

Outer Loop

Runs until dividend becomes smaller than divisor.

Inner Loop

Uses left shift to double values quickly.

Overall Complexity:

O(log n)

---

Space Complexity

O(1)

Because we use only variables and no extra data structures.

---

Key Concepts Used

• Bit Manipulation
• Left Shift Operator (<<)
• Integer Overflow Handling
• Sign Management
• Efficient Subtraction Method