LeetCode #29 — Medium

Divide Two
Integers

A complete visual walkthrough of bit-shift division — from brute force to logarithmic elegance.

The Problem

Problem Statement

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, then return 2³¹ - 1, and if the quotient is strictly less than -2³¹, then return -2³¹.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333.. which is truncated to 3.

Example 2:

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

Step 01

Brute Force — Repeated Subtraction

The most intuitive approach: keep subtracting the divisor from the dividend and count how many times you can do it. Division is just repeated subtraction, after all.

Example: 10 / 3

count = 1

count = 2

count = 3

1 < 3, stop. Answer = 3

This works, but the time complexity is O(dividend / divisor) which can be enormous. Imagine dividing 2,147,483,647 by 1 — that's over 2 billion subtractions!

💡

We need to subtract bigger chunks. Instead of subtracting the divisor one at a time, what if we could double it each time? That's where bit shifting comes in.

Step 02

The Core Insight — Exponential Probing

Think of it like binary long division. Instead of subtracting the divisor once, we keep doubling it (via left bit-shift) until it would exceed the remaining dividend. Then subtract the largest chunk, and repeat.

Bit-Shift Doubling

For divisor = 3, we build a sequence of powers:

3 x 1 = 3 3 << 0

3 x 2 = 6 3 << 1

3 x 4 = 12 3 << 2

3 x 8 = 24 3 << 3

We keep doubling until the next double would exceed the dividend. Then subtract the largest possible chunk and repeat with the remainder. Each outer loop peels off a significant chunk, making it logarithmic.

⚡

Why is this fast? Each inner loop doubles the subtracted amount (exponential growth), so it takes only O(log n) iterations to find the largest chunk. The outer loop runs at most O(log n) times too, since each iteration removes at least half of the remaining value.

Step 03

Walkthrough: 10 / 3

Let's trace through the algorithm step by step, watching the bit-shift probing in action.

Round 1: dvd = 10, dvs = 3

Probe: double the divisor

temp=3, multiple=1 → Can we double? 10 >= 6? Yes! temp=6, multiple=2

Probe again

temp=6, multiple=2 → Can we double? 10 >= 12? No! Stop here.

Subtract the chunk

dvd = 10 - 6 = 4, quotient += 2 → quotient = 2

Round 2: dvd = 4, dvs = 3

Probe: double the divisor

temp=3, multiple=1 → Can we double? 4 >= 6? No! Stop.

Subtract the chunk

dvd = 4 - 3 = 1, quotient += 1 → quotient = 3

Round 3: dvd = 1, dvs = 3

Check: dvd >= dvs?

1 >= 3? No! Exit outer loop. Remainder is 1, discarded.

Result: 10 / 3 = 3 (truncated toward zero)

Step 04

Edge Cases & Overflow

The tricky part of this problem is handling integer overflow correctly, especially with 32-bit signed integers.

Critical Edge Cases

INT_MIN / -1 = overflow

-2,147,483,648 / -1 = 2,147,483,648 which exceeds INT_MAX. Return 2,147,483,647.

Divide by 1

Return the dividend as-is. The algorithm handles this naturally since temp << 1 quickly exceeds the dividend.

Negative numbers

Convert both to absolute values (using long to avoid overflow with INT_MIN), compute, then apply the sign at the end. Use XOR to determine the sign: (a>0) ^ (b>0).

Dividend = 0

The outer loop dvd >= dvs fails immediately, returning 0.

💡

Why use long? Math.abs(Integer.MIN_VALUE) overflows in 32-bit integers because |MIN_VALUE| = 2,147,483,648 > MAX_VALUE = 2,147,483,647. Casting to long first avoids this.

Step 05

Full Annotated Code

class Solution {
    public int divide(int dividend, int divisor) {

        // Edge case: only possible overflow
        if (dividend == Integer.MIN_VALUE && divisor == -1)
            return Integer.MAX_VALUE;

        // Determine sign via XOR
        int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;

        // Work with absolute values as longs (avoid MIN_VALUE overflow)
        long dvd = Math.abs((long)dividend);
        long dvs = Math.abs((long)divisor);

        int quotient = 0;

        while (dvd >= dvs) {
            // Start with divisor x 1
            long temp = dvs, multiple = 1;

            // Double until next double would exceed dividend
            while (dvd >= (temp << 1)) {
                temp <<= 1;       // double the chunk
                multiple <<= 1;   // double the count
            }

            // Subtract the largest chunk found
            dvd -= temp;
            quotient += multiple;
        }

        return sign * quotient;
    }
}

func divide(dividend int, divisor int) int {
    const intMin = -1 << 31
    const intMax = 1<<31 - 1

    // Edge case: only possible overflow
    if dividend == intMin && divisor == -1 {
        return intMax
    }

    // Determine sign via XOR
    negative := (dividend > 0) != (divisor > 0)

    // Work with absolute values as int64 to avoid overflow
    dvd := abs64(int64(dividend))
    dvs := abs64(int64(divisor))

    var quotient int64

    for dvd >= dvs {
        // Start with divisor x 1
        temp, multiple := dvs, int64(1)

        // Double until next double would exceed dividend
        for dvd >= (temp << 1) {
            temp <<= 1     // double the chunk
            multiple <<= 1 // double the count
        }

        // Subtract the largest chunk found
        dvd -= temp
        quotient += multiple
    }

    if negative {
        return int(-quotient)
    }
    return int(quotient)
}

func abs64(x int64) int64 {
    if x < 0 {
        return -x
    }
    return x
}

def divide(dividend: int, divisor: int) -> int:

    INT_MIN, INT_MAX = -2 ** 31, 2 ** 31 - 1

    # Edge case: only possible overflow
    if dividend == INT_MIN and divisor == -1:
        return INT_MAX

    # Determine sign via XOR
    sign = -1 if (dividend > 0) ^ (divisor > 0) else 1

    # Work with absolute values
    dvd = abs(dividend)
    dvs = abs(divisor)

    quotient = 0

    while dvd >= dvs:
        # Start with divisor x 1
        temp, multiple = dvs, 1

        # Double until next double would exceed dividend
        while dvd >= (temp << 1):
            temp <<= 1       # double the chunk
            multiple <<= 1   # double the count

        # Subtract the largest chunk found
        dvd -= temp
        quotient += multiple

    return sign * quotient

impl Solution {
    pub fn divide(dividend: i32, divisor: i32) -> i32 {
        // Edge case: only possible overflow
        if dividend == i32::MIN && divisor == -1 {
            return i32::MAX;
        }

        // Determine sign via XOR
        let negative = (dividend > 0) != (divisor > 0);

        // Work with absolute values as i64 to avoid overflow
        let mut dvd = (dividend as i64).abs();
        let dvs = (divisor as i64).abs();

        let mut quotient: i64 = 0;

        while dvd >= dvs {
            // Start with divisor x 1
            let (mut temp, mut multiple) = (dvs, 1i64);

            // Double until next double would exceed dividend
            while dvd >= (temp << 1) {
                temp <<= 1;     // double the chunk
                multiple <<= 1; // double the count
            }

            // Subtract the largest chunk found
            dvd -= temp;
            quotient += multiple;
        }

        if negative { -(quotient as i32) } else { quotient as i32 }
    }
}

function divide(dividend: number, divisor: number): number {

    const INT_MIN = -(2 ** 31), INT_MAX = 2 ** 31 - 1;

    // Edge case: only possible overflow
    if (dividend === INT_MIN && divisor === -1)
        return INT_MAX;

    // Determine sign via XOR
    const sign = (dividend > 0) !== (divisor > 0) ? -1 : 1;

    // Work with absolute values
    let dvd = Math.abs(dividend);
    let dvs = Math.abs(divisor);

    let quotient = 0;

    while (dvd >= dvs) {
        // Start with divisor x 1
        let temp = dvs, multiple = 1;

        // Double until next double would exceed dividend
        while (dvd >= temp * 2) {
            temp *= 2;       // double the chunk
            multiple *= 2;   // double the count
        }

        // Subtract the largest chunk found
        dvd -= temp;
        quotient += multiple;
    }

    return sign * quotient;
}

Step 06

Interactive Demo

Enter any dividend and divisor to watch the bit-shift probing algorithm work step by step.

Bit-Shift Division Visualizer

dividend

divisor

Press "Step →" or "Run All" to begin.

Step 07

Complexity Analysis

Time

O(log² n)

Space

O(1)

The inner loop doubles the divisor each iteration, taking O(log n) steps to find the largest power-of-two chunk. The outer loop runs at most O(log n) times because each round removes at least half of the remaining dividend. Combined: O(log² n) where n is the dividend. Only a handful of integer variables are used, so space is O(1).

Approach Breakdown

BRUTE FORCE

O(n) time

O(1) space

A single loop subtracts the divisor from the dividend one copy at a time, counting iterations. For dividend n and divisor 1, this performs n subtractions -- O(n) where n is the quotient magnitude. Only a counter and the running remainder are stored.

OPTIMAL

O(log2 n) time

O(1) space

The inner loop doubles the divisor via bit-shift each iteration, finding the largest power-of-two chunk in O(log n) steps. The outer loop runs at most O(log n) times because each round removes at least half the remaining dividend. Combined: O(log² n). Only a handful of integer variables are needed.

🎯

Doubling the divisor each step gives O(log n) iterations, each with O(log n) shifts -- O(log² n) total. For dividend = 2,147,483,647 and divisor = 1, brute force needs ~2 billion subtractions while bit-shift probing needs only ~31 inner iterations total (one per bit).

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Overflow in intermediate arithmetic

Wrong move: Temporary multiplications exceed integer bounds.

Usually fails on: Large inputs wrap around unexpectedly.

Fix: Use wider types, modular arithmetic, or rearranged operations.

Boundary update without `+1` / `-1`

Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.

Usually fails on: Two-element ranges never converge.

Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.

Divide TwoIntegers