LeetCode 29: Divide Two Integers Solution in Python Explained

Problem Statement

LeetCode 29, Divide Two Integers, is a medium-level problem where you’re given two integers, dividend and divisor, and must return their quotient as an integer. The division must be performed without using multiplication, division, or modulo operators, and you need to handle overflow by returning 2^31 - 1 (i.e., 2147483647) if the result exceeds the 32-bit signed integer range (-2^31 to 2^31 - 1).

Constraints

-2^31 <= dividend, divisor <= 2^31 - 1: Both inputs are within 32-bit signed integer bounds.
divisor != 0: Division by zero isn’t possible.

Example

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

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

Input: dividend = -2147483648, divisor = -1
Output: 2147483647
Explanation: -2147483648 ÷ -1 = 2147483648, overflows, so return 2^31 - 1.

Understanding the Problem

How do you solve LeetCode 29: Divide Two Integers in Python without multiplication or division? For dividend = 10 and divisor = 3, you need to determine how many times 3 fits into 10—answer: 3. For negative numbers or edge cases like overflow, extra care is needed. We’ll explore two approaches: a Bit Manipulation Solution (optimal and primary) and an Alternative with Repeated Subtraction (intuitive but slower). The bit manipulation method uses binary shifts to perform division efficiently.

Solution 1: Bit Manipulation Approach (Primary)

Explanation

Since we can’t use multiplication or division, use bit shifting to repeatedly subtract large multiples of the divisor. Convert numbers to positive, track the sign, and handle overflow. The idea is to find how many times the divisor, shifted left (doubled), fits into the dividend.

Here’s a conceptual flow for 10 ÷ 3:

10 - (3 << 1) = 10 - 6 = 4 (count 2)
4 - (3 << 0) = 4 - 3 = 1 (count 1)
Total quotient = 2 + 1 = 3

Handle Edge Case.

If dividend = -2^31 and divisor = -1, return 2^31 - 1 (overflow).

Track Sign and Absolute Values.

Determine result sign, convert to positive numbers.

Bitwise Division.

Shift divisor left to subtract large chunks, build quotient.

Apply Sign and Check Bounds.

Return signed result, capped at 32-bit max.

Step-by-Step Example

Example 1: dividend = 10, divisor = 3

We need quotient 3.

Goal: Compute 10 ÷ 3.
Result for Reference: 3.
Start: dividend = 10, divisor = 3.
Step 1: Check overflow.

Not -2^31 ÷ -1, proceed.

Step 2: Sign = positive (10 > 0, 3 > 0), abs_dividend = 10, abs_divisor = 3.
Step 3: Bitwise division.

Shift 3 left: 3 << 1 = 6, 10 ≥ 6, subtract 10 - 6 = 4, quotient += 2.
Shift 3 left: 3 << 0 = 3, 4 ≥ 3, subtract 4 - 3 = 1, quotient += 1.
1 < 3, stop.
Total quotient = 2 + 1 = 3.

Step 4: Apply sign, 3 is positive, within bounds.
Finish: Return 3.

Example 2: dividend = 7, divisor = -3

We need quotient -2.

Goal: Compute 7 ÷ -3.
Result for Reference: -2.
Start: Sign = negative (7 > 0, -3 < 0), abs_dividend = 7, abs_divisor = 3.
Step 1: Bitwise division.

3 << 1 = 6, 7 ≥ 6, 7 - 6 = 1, quotient += 2.
3 << 0 = 3, 1 < 3, stop.
Quotient = 2.

Step 2: Apply sign, -2.
Finish: Return -2.

How the Code Works (Bit Manipulation)

Here’s the Python code with line-by-line explanation:

def divide(dividend: int, divisor: int) -> int:
    # Line 1: Define 32-bit bounds
    MAX_INT = 2**31 - 1  # 2147483647
    MIN_INT = -2**31     # -2147483648

    # Line 2: Handle overflow case
    if dividend == MIN_INT and divisor == -1:
        return MAX_INT

    # Line 3: Determine sign of result
    sign = -1 if (dividend < 0) ^ (divisor < 0) else 1
    # Line 4: Convert to positive numbers
    abs_dividend = abs(dividend)
    abs_divisor = abs(divisor)

    # Line 5: If dividend < divisor, quotient is 0
    if abs_dividend < abs_divisor:
        return 0

    # Line 6: Initialize quotient
    quotient = 0
    # Line 7: Bitwise division
    while abs_dividend >= abs_divisor:
        curr_divisor = abs_divisor
        multiple = 1
        # Line 8: Shift divisor left
        while abs_dividend >= (curr_divisor << 1):
            curr_divisor <<= 1
            multiple <<= 1
        # Line 9: Subtract and add to quotient
        abs_dividend -= curr_divisor
        quotient += multiple

    # Line 10: Apply sign
    result = sign * quotient
    # Line 11: Ensure within bounds
    return min(MAX_INT, max(MIN_INT, result))

Alternative: Repeated Subtraction Approach

Explanation

Repeatedly subtract the divisor from the dividend until the dividend is less than the divisor, counting subtractions. Handle sign and overflow separately. This is intuitive but slow for large numbers.

Handle Edge Case.

Overflow check for MIN_INT ÷ -1.

Track Sign and Absolute Values.
Subtract and Count.

Subtract divisor, increment quotient.

Return Signed Result.

Step-by-Step Example (Alternative)

For dividend = 10, divisor = 3:

Goal: Quotient = 3.
Result for Reference: 3.
Start: abs_dividend = 10, abs_divisor = 3, sign = 1.
Step 1: 10 ≥ 3, 10 - 3 = 7, quotient = 1.
Step 2: 7 ≥ 3, 7 - 3 = 4, quotient = 2.
Step 3: 4 ≥ 3, 4 - 3 = 1, quotient = 3.
Step 4: 1 < 3, stop.
Finish: Return 3.

How the Code Works (Subtraction)

def divideSubtraction(dividend: int, divisor: int) -> int:
    # Line 1: Define bounds
    MAX_INT = 2**31 - 1
    MIN_INT = -2**31

    # Line 2: Overflow case
    if dividend == MIN_INT and divisor == -1:
        return MAX_INT

    # Line 3: Sign and absolute values
    sign = -1 if (dividend < 0) ^ (divisor < 0) else 1
    abs_dividend = abs(dividend)
    abs_divisor = abs(divisor)

    # Line 4: Quotient counter
    quotient = 0
    # Line 5: Repeated subtraction
    while abs_dividend >= abs_divisor:
        abs_dividend -= abs_divisor
        quotient += 1

    # Line 6: Apply sign
    return sign * quotient

Complexity

Bit Manipulation:

Time: O(log n) – Number of shifts is logarithmic in dividend size.
Space: O(1) – Constant space.

Subtraction:

Time: O(n) – Linear in quotient size, slow for large numbers.
Space: O(1).

Efficiency Notes

Bit manipulation is far faster (O(log n) vs. O(n)), making it the preferred solution for LeetCode 29. Subtraction is simpler but impractical for large inputs like 2147483647 ÷ 1.

Key Insights

Tips to master LeetCode 29:

Bit Shifts are Power: Use doubling to speed up division.
Sign Matters: Handle positive/negative cases cleanly.
Overflow Watch: Always check 32-bit bounds!

Additional Example

For dividend = -15, divisor = 2:

Goal: Quotient = -7.
Bit Manipulation: abs(15) ÷ 2 = 7, sign = -1, return -7.
Result: -7.

Edge Cases

Overflow: -2147483648 ÷ -1 – Return 2147483647.
Zero Dividend: 0 ÷ 5 – Return 0.
Equal Numbers: 6 ÷ 6 – Return 1.

Final Thoughts

The Bit Manipulation solution is the star of LeetCode 29 in Python—efficient and clever, perfect for tackling division without operators. For a related challenge, check out LeetCode 28: Find the Index of the First Occurrence in a String to flex your string skills! Ready to master this problem? Solve LeetCode 29 on LeetCode now and test it with edge cases like negative numbers or overflow to solidify your understanding. Dive in and conquer it!